﻿#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>
#include<stdbool.h>


//在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
//每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

//下述方法难以解决找零钱的过程
//int main()
//{
//	int bull[5] = { 0 };
//	int i = 0;
//	int flag = 1;
//	int sum = 0;
//	for (i = 0; i<5; i++)
//	{
//		scanf("%d", &bull[i]);
//		if ((bull[i] == 5) || (bull[i] == 10) || (bull[i] == 20))
//		{
//			sum += bull[i];
//			if (bull[i] == 10)
//			{
//				//检测还有没有5元的
//				int j = 0;
//				for (j = 0; j < 5; j++)
//				{
//					if (bull[j] == 5)
//					{
//						sum = sum - 5;
//					}
//				}
//			
//			}
//			if (bull[i] == 20)
//			{
//				int j = 0;
//				for (j = 0; j < 5; j++)
//				{
//					if ((bull[j] == 5))
//					{
//						sum = sum - 5;
//					}
//				}
//			}
//		}
//		if (sum<0)
//		{
//			flag = 0;
//		}
//	}
//	if (flag == 1)
//	{
//		printf("true");
//	}
//	else
//	{
//		printf("false");
//	}
//	return 0;
//}
//由于给的钱是固定的，5、10、20，所以我们可以只定义5元10元这些钞票的个数
//int main()
//{
//	int bull[5] = { 0 };
//	int i = 0;
//	int flag = 1;
//	int sum = 0,five=0,ten=0;
//	for (i = 0; i<5; i++)
//	{
//		scanf("%d", &bull[i]);
//		if ((bull[i] == 5) || (bull[i] == 10) || (bull[i] == 20))
//		{
//			if (bull[i] == 5)
//			{
//				five++;
//			}
//			else if (bull[i] == 10)
//			{
//				ten++;
//				five--;
//			}
//			else
//			{
//				if (ten > 0)
//				{
//					ten--;
//					five--;
//				}
//				else
//				{
//					five -= 3;
//				}
//			}
//		}
//		if (five<0)
//		{
//			flag = 0;
//		}
//	}
//	if (flag == 1)
//	{
//		printf("true");
//	}
//	else
//	{
//		printf("false");
//	}
//	return 0;
//}
////转换成函数解决
//bool lemonadeChange(int* bills, int billsSize){
//	int i = 0;
//	int flag = 1;
//	int sum = 0, five = 0, ten = 0;
//	for (i = 0; i<billsSize; i++)
//	{
//		if ((bills[i] == 5) || (bills[i] == 10) || (bills[i] == 20))
//		{
//			if (bills[i] == 5)
//			{
//				five++;
//			}
//			else if (bills[i] == 10)
//			{
//				ten++;
//				five--;
//			}
//			else
//			{
//				if (ten > 0)
//				{
//					ten--;
//					five--;
//				}
//				else
//				{
//					five -= 3;
//				}
//			}
//		}
//		if (five<0)
//		{
//			flag = 0;
//		}
//	}
//	if (flag == 1)
//	{
//		return true;
//	}
//	else
//	{
//		return false;
//	}
//}


//int* twoSum(int* nums, int numsSize, int target, int* returnSize)
//{
//
//	int left = 0;
//	int i = 0;
//	int arr[2] = { 0 };
//	int* ret = arr;
//
//	for (left = 0; left<numsSize; left++)
//	{
//		for (i = left + 1; i<numsSize; i++)
//		{
//			if ((nums[left] + nums[i]) == target)
//			{
//				int arr[2] = { i, left };
//				int* ret = arr;
//				*returnSize = 2;
//				return ret;
//			}
//		}
//
//	}
//	*returnSize = 0;
//	return ret;
//}
//
////通过malloc开辟动态空间，使函数可以返回多个值（即返回一个数组）
//double* convertTemperature(double celsius, int* returnSize){
//	double* ans = (double*)malloc(sizeof(double) * 2);
//	*returnSize = 2;
//	ans[0] = celsius + 273.15;
//	ans[1] = celsius*1.80 + 32.00;
//	return ans;
//}

////给一个n返回其与2的最小公倍数
//int smallestEvenMultiple(int n){
//	if (n % 2 != 0)
//	{
//		return n * 2;
//	}
//	else
//	{
//		return n;
//	}
//}
//
////二叉树（结构体的嵌套使用，使用自身）
////给你一个 二叉树 的根结点 root，该二叉树由恰好 3 个结点组成：根结点、左子结点和右子结点。
////如果根结点值等于两个子结点值之和，返回 true ，否则返回 false 。
///**
//* Definition for a binary tree node.
//* struct TreeNode {
//*     int val;
//*     struct TreeNode *left;
//*     struct TreeNode *right;
//* };
//*/
//
////bool checkTree(struct TreeNode* root){
////	if ((*root).val == root->left->val + root->right->val)
////	{
////		return true;
////	}
////	else
////		return false;
////}}
//
////测试整形的储存
//int main()
//{
//	char a = 128;
//	//10000000
//	unsigned char b = -1;
//	//11111111
//	printf("%d\n", a);
//	printf("%d\n", b);
//
//	return 0;
//}
//
////给你两个整数，n 和 start 。
////数组 nums 定义为：nums[i] = start + 2 * i（下标从 0 开始）且 n == nums.length 。
////请返回 nums 中所有元素按位异或（XOR）后得到的结果。
//
//int xorOperation(int n, int start){
//	int nums[1000] = { 0 };
//	for (int i = 0; i<n; i++)
//	{
//		nums[i] = start + 2 * i;
//	}
//	int sum = 0;
//	for (int i = 0; i<n; i++)
//	{
//		sum ^= nums[i];
//	}
//	return sum;
//}
//
////如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。
////返回好数对的数目。
//int numIdenticalPairs(int* nums, int numsSize){
//	int i = 0;
//	int j = 0;
//	int count = 0;
//	for (i = 0; i<numsSize; i++)
//	{
//		for (j = 1 + i; j<numsSize; j++)
//		{
//			if (nums[i] == nums[j])
//			{
//				count++;
//			}
//		}
//	}
//	return count;
//}
//
////绝对值
//int Jue(int i, int j)
//{
//	if (i - j<0)
//	{
//		return -(i - j);
//	}
//	else
//		return i - j;
//}

////给你一个整数数组 arr ，以及 a、b 、c 三个整数。请你统计其中好三元组的数量。
////如果三元组(arr[i], arr[j], arr[k]) 满足下列全部条件，则认为它是一个 好三元组 。
////0 <= i < j < k < arr.length
////| arr[i] - arr[j] | <= a
////| arr[j] - arr[k] | <= b
////| arr[i] - arr[k] | <= c
////其中 | x | 表示 x 的绝对值。
////绝对值
//int Jue(int i, int j)
//{
//	if (i - j<0)
//	{
//		return -(i - j);
//	}
//	else
//		return i - j;
//}
//
//int countGoodTriplets(int* arr, int arrSize, int a, int b, int c){
//	int i, j, k;
//	int count = 0;
//	for (i = 0; i<arrSize; i++)
//	{
//		for (j = 1 + i; j<arrSize; j++)
//		{
//			for (k = 1 + j; k<arrSize; k++)
//			{
//				if (Jue(arr[i], arr[j]) <= a)
//				{
//					if (Jue(arr[j], arr[k]) <= b)
//					{
//						if (Jue(arr[i], arr[k]) <= c)
//							count++;
//
//					}
//				}
//			}
//		}
//	}
//	return count;
//}

////给你一个字符串 s ，将该字符串中的大写字母转换成相同的小写字母，返回新的字符串。
//char * toLowerCase(char * s){
//	char *ret = s;
//	while ((*s) != '\0')
//	{
//		if ((*s) <= 90 && (*s) >= 65)
//		{
//			(*s) += 32;
//		}
//		s++;
//	}
//	return ret;
//}
//
////给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。返回这个结果。
//int addDigits(int num){
//	while (num >= 10)
//	{
//		num = num / 10 + num % 10;
//	}
//	return num;
//}
//
////给你一个整数 n，请你帮忙计算并返回该整数「各位数字之积」与「各位数字之和」的差。
//int subtractProductAndSum(int n){
//	int sub = 1;
//	int m = n;
//	int sum = 0;
//	//乘
//	while (n)
//	{
//		sub *= n % 10;
//		n /= 10;
//	}
//	while (m)
//	{
//		sum += m % 10;
//		m /= 10;
//	}
//	return sub - sum;
//}





////比特c语言初阶考试
//int main() {
//	int a = 0, b = 0;
//	scanf("%d %d", &a, &b);
//	int max = 1;
//	max = a > b ? a : b;
//	int i = 1;
//	for (int i = max; i < a*b;i++)
//	{
//		if ((i % a == 0) && (i % b == 0))
//		{
//			break;
//		}
//	}
//	printf("%d", i);
//}
//int main()
//{
//	int a, b;
//	int n = 1;
//	scanf("%d %d", &a, &b);
//	while (a*n%b!=0)
//	{
//		n++;
//	}
//	printf("%d", a*n);
//	return 0;
//}
//
//#include<stdio.h>
//
//int main() {
//	char word[100] = { 0 };
//	gets(word);
//	//printf("%s", word);
//	int sz = strlen(word)-1;
//
//	while (sz)
//	{ 
//		if (word[sz] == ' ')
//		{
//			printf("%s ", &word[sz+1]);
//			word[sz] = '\0';
//
//		}
//		if (sz == 0)
//		{
//			break;
//		}
//		sz--;
//	}
//	printf("%s", &word[sz]);
//	return 0;
//}


////给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。
////如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。
//#include<math.h>
////方法1：用x表示次方，sum表示pow后返回的值，让其与n进行比较，若二者在某一次相等了，就返回true；若直到sum>n了之，if条件任然没触发，跳出循环，返回false
//bool isPowerOfTwo(int n){
//	int x = 0;
//	long long sum = 0;
//	for (x = 0, sum; sum<n; x++)
//	{
//		sum = (long long)pow(2, x);
//		if (sum == n)
//		{
//			return true;
//		}
//	}
//	return false;
//}
////方法2：由于2的次方的二进制表示只有一个1其余位都是0，所以我们可以利用这个特点，让n&（n-1），然后判断是否是0（只有2的次方才会为0）
//bool isPowerOfTwo(int n){
//	return n>0 && (n&(n - 1)) == 0;//&&逻辑与的优先级比==判断相等的优先级低
//}
////方法3：由于2的次方的二进制表示只有一个1其余位都是0，当二进制位只有一个1时，n&-n就会等于n，即只有原数二进制有的1的部分留下来
////比如： 1=00000000000000000000000000000001 
////		-1=11111111111111111111111111111111		这两者进行&按位与时，只会留下1
////		 2=00000000000000000000000000000010
////		-2=11111111111111111111111111111110		2&（-2）=2	
////根据这一特性，我们又可以写出新的解法
//bool isPowerOfTwo(int n){
//	return n>0 && (n&(-n)) == n;
//}
//
////给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。
////整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3x
////方法1
//#include<math.h>
//bool isPowerOfThree(int n){
//	int x = 0;
//	long long sum = 0;
//	for (x = 0, sum = 0; sum<n; x++)
//	{
//		sum = (long long)pow(3, x);
//		if (sum == n)
//		{
//			return true;
//		}
//	}
//	return false;
//}
////方法2
////若这个数是3的次方，那他一直除以3，最后只能为3/3=1，比如6/3=2不为1就返回false
//bool isPowerOfThree(int n){
//	while (n != 0 && n % 3 == 0)
//	{
//		n /= 3;
//	}
//	return n == 1;
//}

////尝试二维数组的传递
////void print(int* p)
////{
////	int i = 0;
////	for (i = 0; i < 6; i++)
////	{
////		printf("%d", p);
////	}
////}
//void print(int(*p)[3])
//{
//	int i = 0;
//	for (i = 0; i < 2; i++)
//	{
//		int j = 0;
//		for (j = 0;j < 3; j++)
//		{
//		printf("%d", *(*(p+i)+j));
//
//		printf("%d", p[i][j]);
//		}
//
//	}
//}
//int main()
//{
//	int arr[2][3] = { { 1, 2, 3 }, { 4, 5, 6 } };
//	print(arr);
//}


////判断是否为丑数
//bool isUgly(int n){
//	if (n == 1 || n == 2 || n == 3 || n == 5)
//	{
//		return true;
//	}
//	if (n % 2 == 0)
//	{
//		while (n>1)
//		{
//			if (n / 2 == 3 || n / 2 == 5 || n / 2 == 2)
//			{
//				return true;
//			}
//			n /= 2;
//			if (n % 2 != 0 && n % 3 != 0 && n % 5 != 0)
//			{
//				break;
//			}
//		}
//	}
//	else if (n % 3 == 0)
//	{
//		while (n>2)
//		{
//			if (n / 3 == 2 || n / 3 == 5 || n / 3 == 3)
//			{
//				return true;
//			}
//			n /= 3;
//			if (n % 2 != 0 && n % 3 != 0 && n % 5 != 0)
//			{
//				break;
//			}
//		}
//	}
//	else if (n % 5 == 0)
//	{
//		while (n>4)
//		{
//			if (n / 5 == 2 || n / 5 == 3 || n / 5 == 5)
//			{
//				return true;
//			}
//			n /= 5;
//			if (n % 2 != 0 && n % 3 != 0 && n % 5 != 0)
//			{
//				break;
//			}
//		}
//	}
//	return false;
//}
////更新上述代码，上述代码有错误
//bool isUgly(int n){
//	if (n>0)
//	{
//		if (n == 1 || n == 2 || n == 3 || n == 5)
//		{
//			return true;
//		}
//		while (n % 2 == 0 || n % 3 == 0 || n % 5 == 0)
//		{
//			if (n % 2 == 0)
//			{
//				if (n / 2 == 3 || n / 2 == 5 || n / 2 == 2)
//				{
//					return true;
//				}
//				n /= 2;
//			}
//			else if (n % 3 == 0)
//			{
//				if (n / 3 == 3 || n / 3 == 5 || n / 3 == 2)
//				{
//					return true;
//				}
//				n /= 3;
//			}
//			else if (n % 5 == 0)
//			{
//				if (n / 5 == 3 || n / 5 == 2 || n / 5 == 5)
//				{
//					return true;
//				}
//				n /= 5;
//			}
//		}
//	}
//	return false;
//}


////给你一个数组 nums ，数组中有 2n 个元素，按[x1, x2, ..., xn, y1, y2, ..., yn] 的格式排列。
////请你将数组按[x1, y1, x2, y2, ..., xn, yn] 格式重新排列，返回重排后的数组。
//#include<stdlib.h>
//int* shuffle(int* nums, int numsSize, int n, int* returnSize)
//{
//	int i = 0;//用于控制ret数组
//	int* ret = (int*)malloc(sizeof(int)*numsSize);
//	int j = 0;//控制n之前的数字
//	int k = n;//控制n之后的数字
//	*returnSize = numsSize;//返回的
//	for (i = 0, j = 0, k = n; j<n; j++, k++, i += 2)
//	{
//		ret[i] = nums[j];
//		ret[i + 1] = nums[k];
//	}
//	return ret;
//}


////给你一个由若干 0 和 1 组成的字符串 s ，请你计算并返回将该字符串分割成两个 非空 子字符串（即 左 子字符串和 右 子字符串）所能获得的最大得分。
////「分割字符串的得分」为 左 子字符串中 0 的数量加上 右 子字符串中 1 的数量。
//int maxScore(char * s){
//	int max = 0;
//	int i = 0;
//	int len = strlen(s);
//	int left = 1;
//	while (left<len)
//	{
//		int count = 0;
//		for (i = 0; i<left; i++)
//		{
//			if (s[i] == '0')
//			{
//				count++;
//			}
//		}
//		for (i = left; i<len; i++)
//		{
//			if (s[i] == '1')
//			{
//				count++;
//			}
//		}
//		max = max>count ? max : count;
//		left++;
//	}
//	return max;
//}


////给你一个下标从 0 开始的字符串数组 words 和两个整数：left 和 right 。
////如果字符串以元音字母开头并以元音字母结尾，那么该字符串就是一个 元音字符串 ，其中元音字母是 'a'、'e'、'i'、'o'、'u' 。
////返回 words[i] 是元音字符串的数目，其中 i 在闭区间[left, right] 内。
//int isyuan(char a)
//{
//	if (a == 'a' || a == 'e' || a == 'i' || a == 'o' || a == 'u')
//	{
//		return 1;
//	}
//	return 0;
//}
//int vowelStrings(char ** words, int wordsSize, int left, int right)
//{
//	int count = 0;
//	char first, end;
//	while (left <= right)
//	{
//		int len = strlen(words[left]);
//		first = words[left][0];
//		end = words[left][len - 1];
//		if (isyuan(first))
//		{
//			if (isyuan(end))
//			{
//				count++;
//			}
//		}
//		left++;
//	}
//	return count;
//}


////符合下列属性的数组 arr 称为 山脉数组 ：
////arr.length >= 3
////存在 i（0 < i < arr.length - 1）使得：
////arr[0] < arr[1] < ... arr[i - 1] < arr[i]
////arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
////给你由整数组成的山脉数组 arr ，返回满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i 。
////你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。
//int peakIndexInMountainArray(int* arr, int arrSize)
//{
//	int i = 1;
//	for (i = 1; i + 1<arrSize; i++)
//	{
//		if (arr[i - 1]<arr[i] && arr[i]>arr[i + 1])
//		{
//			break;
//		}
//	}
//	return i;
//}


////给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
////请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
////注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
//void charlu(int *nums1, int j, int* k, int n)
//{
//	int a = 0;
//	a = *k;
//	while (a != j)
//	{
//		nums1[a] = nums1[a - 1];
//		a--;
//	}
//	nums1[j] = n;
//	(*k)++;
//}
//void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
//{
//	int i = 0;
//	int j = 0;
//	for (i = 0; i<nums2Size; i++)
//	{
//		for (j = 0; j<nums1Size; j++)
//		{
//			if (nums2[i]<nums1[j])
//			{
//				charlu(nums1, j, &m, nums2[i]);
//				break;
//			}
//			if (j == m)
//			{
//				nums1[j] = nums2[i];
//				m++;
//				break;
//			}
//		}
//	}
//}


////给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
////不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
////元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
//int removeElement(int* nums, int numsSize, int val)
//{
//	int len = 0;
//	int left = 0;
//	int right = numsSize - 1;
//	//算返回的长度
//	for (left = 0; left<numsSize; left++)
//	{
//		if (nums[left] != val)
//		{
//			len++;
//		}
//	}
//	//找前面是val的，后面不是val的值进行交换
//	for (left = 0; left<numsSize; left++)
//	{
//		if (nums[left] == val)
//		{
//			while (right >= 0)
//			{
//				if (nums[right] != val)
//				{
//					int tmp = nums[right];
//					nums[right] = nums[left];
//					nums[left] = tmp;
//					right--;
//					break;
//				}
//				right--;
//			}
//		}
//		//三种情况结束：1.left和right已经贴在一起了。2.left和right相等了。3.left前的数（包括left前的数）数字数量已经等于len的长度
//		if (right - left == 1 || left == right || left + 1 == len)
//		{
//			break;
//		}
//	}
//	return len;
//}


////给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
////考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
////更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
////返回 k 。
//int removeDuplicates(int* nums, int numsSize)
//{
//	int* ret = (int*)malloc(sizeof(int)*numsSize);
//	int i = 0;
//	int count = 0;
//	ret[count++] = nums[0];
//	//把不同的存入ret中
//	for (i = 0; i<numsSize; i++)
//	{
//		if (nums[i] != ret[count - 1])
//		{
//			ret[count++] = nums[i];
//		}
//	}
//	//把ret的钱count个元素，复制给nums
//	for (i = 0; i<count; i++)
//	{
//		nums[i] = ret[i];
//	}
//	return count;
//}

//int main()
//{
//	int arr['0'];
//	int brr['1'];
//	int crr['10'];
//	int drr['100'];
//	//int err['1000'];
//	//int frr['10000'];
//}


//给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
//不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

//交换函数，把多余的数字放到最后去，再把所有数字向前移动一位
void swap(int* nums, int n, int i, int numsSize)
{
	while (1)
	{
		nums[i] = nums[i + 1];
		i++;
		if (i == numsSize - 1)
		{
			nums[i] = n;
			break;
		}
	}
}
//用于检测从i开始后面的元素是否都相等，若都相等则返回1，不相等返回0
int IsSame(int *nums, int numsSize, int i)
{
	int count1 = 0;
	int first = nums[i];
	int n = i;
	for (i; i<numsSize; i++)
	{
		if (nums[i] == first)
		{
			count1++;
		}
	}
	if (count1 == numsSize - n)
	{
		return 1;
	}
	else
		return 0;
}
int removeDuplicates(int* nums, int numsSize)
{
	int i = 0, time = 0;//i作为循环下标，time是记录同个数字出现的次数
	int text = nums[0];//text用于检测相等
	int count = 0;//count用于最后返回的数组长度
	//numsSize原本就小于等于2，则不用进入后续循环，直接退出就行
	if (numsSize <= 2)
	{
		return numsSize;
	}
	//检测从第一个元素（下标0）开始，后续元素是否全部相等，若相等直接返回2
	if (IsSame(nums, numsSize, 0))
	{
		return 2;
	}
	//检测部分
	for (i = 0; i<numsSize; i++)
	{
		//由于数组是升序的，所有若某次检测到当前数字比前一个小，则直接结束循环。
		if (i >= 1 && nums[i]<nums[i - 1])
		{
			break;
		}
		//相等time++,若出现的次数小于等于2，则count++
		if (nums[i] == text)
		{
			time++;
			if (time <= 2)
			{
				count++;
			}
		}
		//若nums[i]不等于text，则说明到了一个新的数字，把text重新改变time归1，count+1
		else
		{
			text = nums[i];
			time = 1;
			count++;
		}
		//如果出现次数大于2，并且不是最后一个元素，则进入交换函数
		if (time>2 && i != numsSize - 1)
		{
			swap(nums, nums[i], i, numsSize);
			//交换后，把i-1，这样在后续回归到上面i++可相互抵消，实现重新检测交换后的当前位置
			i = i - 1;
			//若交换后的数组当前数字还是和交换前的数字相等，则检测一下后续的数字是否都相等
			if (nums[i] == text)
			{
				if (IsSame(nums, numsSize, i))
				{
					break;
				}
			}
		}
		//当前面都没有结束时，那么我们检测到最后一个元素了，也该退出循环
		if (i == numsSize - 1)
		{
			break;
		}
	}
	return count;
}

#include<stdlib.h>
//给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n / 2 ⌋ 的元素。
//你可以假设数组是非空的，并且给定的数组总是存在多数元素。
int compare(const void*e1, const void*e2)
{
	return *(int*)e1 - *(int*)e2;
}
int majorityElement(int* nums, int numsSize)
{
	int i = 0;
	qsort(nums, numsSize, sizeof(int), compare);
	int n = nums[0];
	int count = 0;
	for (i = 0; i<numsSize; i++)
	{
		if (nums[i] == n)
		{
			count++;
		}
		else
		{
			n = nums[i];
			count = 1;
		}
		if (count>numsSize / 2)
		{
			break;
		}
	}
	return n;
}


//189.给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
//翻转函数，i是首地址，n是末尾地址
void reverse(int *nums, int i, int n)
{
	while (i<n)
	{
		int tmp = nums[i];
		nums[i] = nums[n];
		nums[n] = tmp;
		i++;
		n--;
	}
}
void rotate(int* nums, int numsSize, int k)
{
	//如果numsSize为一，或者k=numssize，则直接返回
	if (numsSize == 1 || numsSize == k)
	{
		return;
	}
	//k比numsize小的情况（正常情况）
	if (k<numsSize)
	{
		reverse(nums, 0, numsSize - 1);
		reverse(nums, 0, k - 1);
		reverse(nums, k, numsSize - 1);
		return;//由于可能有递归的情况，所以要加个返回
	}
	//特殊情况，k比numssize大
	else
	{
		//不断去减去numssize，直到k<numssize，再执行一次函数
		while (k>numsSize)
		{
			k -= numsSize;
		}
		rotate(nums, numsSize, k);
		return;
	}
}


//121
//给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
//你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
//返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
//暴力解法
int maxProfit(int* prices, int pricesSize)
{
	if (pricesSize <= 20)
	{
		int a, b;
		int sum = 0;
		for (a = pricesSize - 1; a >= 1; a--)
		{
			for (b = a - 1; b >= 0; b--)
			{
				if (prices[b]<prices[a])
				{
					sum = sum>(prices[a] - prices[b]) ? sum : (prices[a] - prices[b]);
				}
			}
		}
		return sum;
	}
	else
	{
		int flag = 0;
		for (int m = 0; m<pricesSize - 1; m++)
		{
			if (prices[m]<prices[m + 1])
			{
				flag = 1;
			}
		}
		if (flag == 0)
		{
			return 0;
		}
		//找min1与之后的最大值相减得到sum_min
		int left;
		int min1 = prices[0], max1 = 0;
		int sum_min = 0, sum_max = 0;
		//找到最小值
		for (left = 0; left<pricesSize; left++)
		{
			min1 = min1<prices[left] ? min1 : prices[left];
		}
		//找到最小值在数组中位置
		for (left = 0; left<pricesSize; left++)
		{
			if (min1 == prices[left])
			{
				break;
			}
		}
		//如果最小值在最后一位,sum_min=0
		if (left == pricesSize - 1)
		{
			sum_min = 0;
		}
		//最小值不在最后一位，从最小值往后找其中的最大值，二者相减得到sum_min的最大值
		for (left; left<pricesSize; left++)
		{
			max1 = max1>prices[left] ? max1 : prices[left];
		}
		sum_min = max1 - min1;

		//找max2前的最小值，相减得到sum_max
		int i;
		int min2 = prices[0], max2 = 0;
		//找最大值
		for (i = 0; i<pricesSize; i++)
		{
			max2 = max2>prices[i] ? max2 : prices[i];
		}
		//找最大值的位置
		for (i = 0; i<pricesSize; i++)
		{
			if (max2 == prices[i])
			{
				break;
			}
		}
		//最大值在第一位，sum_max=0
		if (i == 0)
		{
			sum_max = 0;
		}
		//从最大值的位置往前找最小值
		for (int j = 0; j<i; j++)
		{
			min2 = min2<prices[j] ? min2 : prices[j];
		}
		sum_max = max2 - min2;
		if (sum_max == 0 && sum_min == 0)
		{
			return maxProfit(prices, pricesSize - 1);
		}
		return sum_max<sum_min ? sum_min : sum_max;
	}
}
////优化后的代码
//int maxProfit(int* prices, int pricesSize)
//{
//	int sum = 0;
//	int min = prices[0];
//	for (int i = 0; i<pricesSize; i++)
//	{
//		//找到从前开始往后的最小值，找到后不断的与后面做差值
//		//若最小值在最后一位，也不会对前面已经求出来的利润产生影响
//		if (prices[i]<min)
//		{
//			min = prices[i];
//		}
//		//对利润进行不断的判断，只取利润大的那种情况
//		if (prices[i] - min>sum)
//		{
//			sum = prices[i] - min;
//		}
//	}
//	return sum;
//}


////122. 买卖股票的最佳时机 II
////给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
////在每一天，你可以决定是否购买和 / 或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
////返回 你能获得的 最大 利润 。
//int maxProfit(int* prices, int pricesSize)
//{
//	int min = prices[0];
//	int sum = 0;
//	for (int i = 0; i<pricesSize; i++)
//	{
//		if (prices[i]<min)
//		{
//			min = prices[i];
//		}
//		if (prices[i] - min>0)
//		{
//			sum += prices[i] - min;
//			min = prices[i];
//		}
//	}
//	return sum;
//}

//int main()
//{
//	int n = 9;
//	float *pFloat = (float*)&n;
//	printf("n的值：%d\n", n);
//	printf("pFloat的值：%f\n", *pFloat);
//	printf("\n");
//	*pFloat = 9.0;
//	//9.0=1001.0
//	//1.001*2^3
//	//	S		M	 E
//	//(-1)^0*1.001*2^3
//
//	//0  1000010 00100000000000000000000
//
//	printf("新n的值为：%d\n", n);
//	printf("新pFloat的值为：%f\n", *pFloat);
//	return 0;
//}



////错误
//bool canJump(int* nums, int numsSize)
//{
//	int point = nums[0];
//	int i = 0;
//	if (point >= numsSize)
//	{
//		return true;
//	}
//	while (i<numsSize - 1)
//	{
//		i += point;
//		if (i >= numsSize - 1)
//		{
//			return true;
//		}
//		point = nums[i];
//		if (point == 0)
//		{
//			if (i >= 1 && nums[i - 1]>1)
//			{
//				point = nums[i - 1];
//			}
//			else
//			{
//				return false;
//			}
//		}
//	}
//	return true;
//}
////错误
//bool canJump(int* nums, int numsSize)
//{
//	int point = nums[0];
//	int i = 0;
//	if (point >= numsSize || numsSize == 1)
//	{
//		return true;
//	}
//	if (point == 0)
//	{
//		return false;
//	}
//	for (i = 0; i<numsSize - 1; i++)
//	{
//		if (nums[i] >= numsSize - 1 - i)
//		{
//			return true;
//		}
//		if (nums[i] == 1 && nums[i + 1] == 0 && i + 1 != numsSize - 1)
//		{
//			return false;
//		}
//	}
//	return false;
//}
//正确解法
//55. 跳跃游戏
//给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
//判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
bool canJump(int* nums, int numsSize)
{
	int first = nums[0];//首先要判断第一个元素
	int i = 0, j = 0;
	//如果第一个元素大于等于numsSize-1就说明可以直接走到最后一位
	//或者整个数组只有一个元素，那就直接返回true
	if (first >= numsSize - 1 || numsSize == 1)
	{
		return true;
	}
	//判断第一个元素是否为0，为0，且上述判断过，numsSize不等于1，则直接返回false
	if (first == 0)
	{
		return false;
	}
	//遍历一边数组找nums[i]=0的位置
	for (i = 0; i<numsSize; i++)
	{
		//找到等于0的位置进入
		if (nums[i] == 0)
		{
			//如果这个进入的位置已经是最后一位，则直接返回true
			if (i == numsSize - 1)
			{
				return true;
			}
			//0不是最后一位，遍历nums[i]前面的元素
			for (j = i - 1; j >= 0; j--)
			{
				//找到0~i-1之间，nums[j](移动步数)>i-j（当前j下标元素的位置和i下标的位置之间的差值）
				//如果找到了这个数，则直接退出
				if (nums[j]>i - j)
				{
					break;
				}
			}
			//判断上面的循环是遍历完结束的还是找到了可以跳过的元素
			//若j=-1，则说明遍历完了0~i-1之间的元素，没有一个符合条件，直接返回false
			if (j == -1)
			{
				return false;
			}
			//if条件没成立，则重新循环，i++，去遍历后面的元素
		}
		//i一直在+1，如果某次i=numssize-1，则说明走到了最后一位，返回true
		if (i == numsSize - 1)
		{
			return true;
		}
	}
	return false;
}


//27.移除元素
//给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
//不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
//元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
//优化方案1	优化后时间复杂度为：O(N),空间复杂度为O(1)
int removeElement(int* nums, int numsSize, int val)
{
	int len1 = 0;
	int len2 = 0;
	int left = 0;
	int right = numsSize - 1;
	//算返回的长度
	for (left = 0; left<numsSize; left++)
	{
		if (nums[left] != val)
		{
			len1++;
		}
	}
	for (left = 0, right; left<numsSize; left++)
	{
		if (nums[left] != val)
		{
			len2++;
		}
		else
		{
			int tmp = nums[right];
			nums[right] = nums[left];
			nums[left] = tmp;
			right--;
			left--;
		}
		if (len1 == len2)
		{
			break;
		}
	}
	return len1;
}
//优化方案2：双指针
int removeElement1(int* nums, int numsSize, int val)
{
	//用i、j两个变量去对应着下标，实现两个for
	int i = 0; int j = 0;
	int len = 0;
	//若i到了最后一个元素，则说明遍历完毕，跳出循环
	while (i<numsSize)
	{
		//先判断nums[j]与nums[i]是不是不等于val，是则len、i、j都+1，指向后面一个元素
		if (nums[j] != val&&nums[i] != val)
		{
			len++;
			j++;
			i++;
		}
		//若某次情况下，nums[j]与nums[i]都指向了val，则i++，j不变，用i去找后面不等于val的值
		else if (nums[j] == val&&nums[i] == val)
		{
			i++;
		}
		//找到nums[j]==val且nums[i]！=val的两个值，交换二者，在把j++，然后把i重新指向j，len也要++
		else
		{
			int tmp = nums[i];
			nums[i] = nums[j];
			nums[j] = tmp;
			j++;
			i = j;
			len++;
		}
	}
	return len;
}


//26. 删除有序数组中的重复项
//给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
//考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
//更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
//返回 k 。
//旧版，会额外开辟空间
int removeDuplicates2(int* nums, int numsSize)
{
	int* ret = (int*)malloc(sizeof(int)*numsSize);
	int i = 0;
	int count = 0;
	ret[count++] = nums[0];
	//把不同的存入ret中
	for (i = 0; i<numsSize; i++)
	{
		if (nums[i] != ret[count - 1])
		{
			ret[count++] = nums[i];
		}
	}
	//把ret的前count个元素，复制给nums
	for (i = 0; i<count; i++)
	{
		nums[i] = ret[i];
	}
	return count;
}
//优化后	双指针
int removeDuplicates3(int* nums, int numsSize)
{
	int i = 1, j = 0;
	while (i<numsSize)
	{
		//若两者相同，则i动
		if (nums[i] == nums[j])
		{
			i++;
		}
		//某次两者不同了，把j+1，然后再把新的值赋给j，i再去找不同的数组
		else
		{
			j++;
			nums[j] = nums[i];
			i++;
		}
	}
	return j + 1;
}


//45. 跳跃游戏 II
//给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
//每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
//0 <= j <= nums[i]
//i + j < n
//返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
int jump(int* nums, int numsSize)
{
	int i = 0;
	//要返回的步数
	int step = 0;
	//k表示我们要跳到的位置的下标，刚开始为最后一位，即numssize-1
	int k = numsSize - 1;
	//先判断一下数组是否只有1位，只有1位则直接返回0
	if (numsSize == 1)
	{
		return 0;
	}
	//数组不止一位，开始循环找
	for (i = 0; i<numsSize; i++)
	{
		//首先第一次进来，k为最后一位元素的下标，我们要找能否能直接跳到最后一位下标的数，找到了就进入
		if (nums[i] >= k - i)
		{
			//把被找到的i赋给k（后续就同理，找能一步到新的k的位置的数的下标i）
			k = i;
			//step加1步
			step++;
			//判断一下，k是否被赋予成0了，若为0，则说明到了第一个元素，则要退出
			if (k == 0)
			{
				break;
			}
			//i要重新判断，所以赋予为-1（为-1很关键，这样回到上面i++后，i就等于0，从数组第一个元素重新遍历）
			i = -1;
		}
	}
	return step;
}
//int main()
//{
//	int nums[5] = { 2,3,1,1,4 };
//	jump(nums, 5);
//	return 0;
//}


////274. H 指数
////给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。
////根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且每篇论文 至少 被引用 h 次。如果 h 有多种可能的值，h 指数 是其中最大的那个。
//int cmp(int *a, int *b) {
//	return *a - *b;
//}
//int hIndex(int *citations, int citationsSize) {
//	qsort(citations, citationsSize, sizeof(int), cmp);
//	int h = 0, i = citationsSize - 1;
//	//这样控制h不会大于citationsSize，
//	while (i >= 0 && citations[i] > h) {
//		h++;
//		i--;
//	}
//	return h;
//}


//88. 合并两个有序数组
//给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
//请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
//注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
//优化后	时间复杂度O(N)
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
	int i = m - 1;
	int j = n - 1;
	int k = n + m - 1;
	while (i >= 0 && j >= 0)
	{
		if (nums1[i]>nums2[j])
		{
			nums1[k] = nums1[i];
			i--; k--;
		}
		else
		{
			nums1[k] = nums2[j];
			j--; k--;
		}
	}
	while (j >= 0)
	{
		nums1[k] = nums2[j];
		j--; k--;
	}
}



////134. 加油站
////在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
////你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i + 1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
////给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 - 1 。如果存在解，则 保证 它是 唯一 的。
//int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize)
//{
//	int i = 0;
//	int* arr = (int*)malloc(sizeof(int)*gasSize);
//	int sum = 0;
//	for (i = 0; i<gasSize; i++)
//	{
//		arr[i] = gas[i] - cost[i];
//		sum += arr[i];
//	}
//	if (sum<0)
//	{
//		return -1;
//	}
//	else
//	{
//		int first = 0;
//		i = 0;
//		int time = 0;
//		while (time != gasSize)
//		{
//			first += arr[i];
//			if (first<0)
//			{
//				i++;
//				first = 0;
//				time = 0;
//				continue;
//			}
//			i++;
//			time++;
//			if ((time <= gasSize) && (i == gasSize))
//			{
//				i = 0;
//			}
//		}
//	}
//	return i;
//}
//int main()
//{
//	int gas[5] = { 1,2,3,4,5 };
//	int cost[5] = { 3,4,5,1,2};
//	canCompleteCircuit(gas, 5, cost, 5);
//	return 0;
//}


////135. 分发糖果
////n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
////你需要按照以下要求，给这些孩子分发糖果：
////每个孩子至少分配到 1 个糖果。
////相邻两个孩子评分更高的孩子会获得更多的糖果。
////请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
//int candy(int* ratings, int ratingsSize){
//	//首先起始每个人糖果为1
//	int candies = ratingsSize;
//	//左遍历的糖果数
//	int* left = (int*)calloc(ratingsSize, sizeof(int));
//	//右遍历的糖果数
//	int* right = (int*)calloc(ratingsSize, sizeof(int));
//	//左遍历
//	for (int i = 1; i<ratingsSize; i++)
//	{
//		//从左往右，比较当前评分和前一个孩子的评分
//		if (ratings[i]>ratings[i - 1])
//		{
//			left[i] = left[i - 1] + 1;
//		}
//	}
//	//右遍历
//	for (int j = ratingsSize - 2; j >= 0; j--)
//	{
//		if (ratings[j]>ratings[j + 1])
//		{
//			right[j] = right[j + 1] + 1;
//		}
//	}
//	for (int k = 0; k<ratingsSize; k++)
//	{
//		//只去左右遍历中大的部分
//		candies += left[k]>right[k] ? left[k] : right[k];
//	}
//	return candies;
//}


////13. 罗马数字转整数
////罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
////	字符          数值
////	I             1
////	V             5
////	X             10
////	L             50
////	C             100
////	D             500
////	M             1000
////	例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。
////	通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
////	I 可以放在 V(5) 和 X(10) 的左边，来表示 4 和 9。
////	X 可以放在 L(50) 和 C(100) 的左边，来表示 40 和 90。
////	C 可以放在 D(500) 和 M(1000) 的左边，来表示 400 和 900。
////	给定一个罗马数字，将其转换成整数。
//int romanToInt(char * s)
//{
//	int sz = strlen(s);
//	int sum = 0;
//	for (int i = 0; i<sz; i++)
//	{
//		if (s[i] == 'I')
//		{
//			sum++;
//		}
//		else if (s[i] == 'V')
//		{
//			sum += 5;
//		}
//		else if (s[i] == 'X')
//		{
//			sum += 10;
//		}
//		else if (s[i] == 'L')
//		{
//			sum += 50;
//		}
//		else if (s[i] == 'C')
//		{
//			sum += 100;
//		}
//		else if (s[i] == 'D')
//		{
//			sum += 500;
//		}
//		else
//		{
//			sum += 1000;
//		}
//	}
//	for (int i = 1; i<sz; i++)
//	{
//		if (s[i - 1] == 'I'&&s[i] != 'I')
//		{
//			sum -= 2;
//		}
//		else if (s[i - 1] == 'V'&&s[i] != 'I'&&s[i] != 'V')
//		{
//			sum -= 10;
//		}
//		else if (s[i - 1] == 'X'&&s[i] != 'I'&&s[i] != 'V'&&s[i] != 'X')
//		{
//			sum -= 20;
//		}
//		else if (s[i - 1] == 'L'&&s[i] != 'I'&&s[i] != 'V'&&s[i] != 'X'&&s[i] != 'L')
//		{
//			sum -= 100;
//		}
//		else if (s[i - 1] == 'C'&&s[i] != 'I'&&s[i] != 'V'&&s[i] != 'X'&&s[i] != 'L'&&s[i] != 'C')
//		{
//			sum -= 200;
//		}
//		else if (s[i - 1] == 'D'&&s[i] != 'I'&&s[i] != 'V'&&s[i] != 'X'&&s[i] != 'L'&&s[i] != 'C'&&s[i] != 'D')
//		{
//			sum -= 1000;
//		}
//	}
//	return sum;
//}
////优化
////把冗余的if改为简洁的Switch case语句
//int romanToInt(char * s)
//{
//	int sz = strlen(s);
//	int sum = 0;
//	//表示循环当前的数字
//	int cur = 0;
//	//先把last设置成最大的M的值，让首个数字必须加上
//	int last = 1000;
//	for (int i = 0; i<sz; i++)
//	{
//		switch (s[i])
//		{
//		case 'I':
//			cur = 1;
//			break;
//		case 'V':
//			cur = 5;
//			break;
//		case 'X':
//			cur = 10;
//			break;
//		case 'L':
//			cur = 50;
//			break;
//		case 'C':
//			cur = 100;
//			break;
//		case 'D':
//			cur = 500;
//			break;
//		case 'M':
//			cur = 1000;
//			break;
//		}
//		if (cur <= last)
//		{
//			sum += cur;
//		}
//		else
//		{
//			//sum+=上本次与上一次的值的差值，得到我们实际需要加上的数字
//			sum += cur - last;
//			//要减掉上一次循环时加上的值
//			sum -= last;
//		}
//		last = cur;
//	}
//	return sum;
//}
//int main()
//{
//	int* s = "MCMXCIV";
//	romanToInt(s);
//	return 0;
//}


////12. 整数转罗马数字
////例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。
////通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
////I 可以放在 V(5) 和 X(10) 的左边，来表示 4 和 9。
////X 可以放在 L(50) 和 C(100) 的左边，来表示 40 和 90。
////C 可以放在 D(500) 和 M(1000) 的左边，来表示 400 和 900。
////给你一个整数，将其转为罗马数字。
//char * intToRoman(int num)
//{
//	char* arr = (char*)malloc(sizeof(char) * 100);
//	int i = 0;
//	while (num)
//	{
//		if (num<5)
//		{
//			if (num != 4)
//			{
//				arr[i++] = 'I';
//				num--;
//			}
//			else
//			{
//				arr[i++] = 'I';
//				arr[i++] = 'V';
//				num -= 4;
//			}
//		}
//		else if (5 <= num&&num<10)
//		{
//			if (num == 9)
//			{
//				arr[i++] = 'I';
//				arr[i++] = 'X';
//				num -= 9;
//			}
//			else{
//				arr[i++] = 'V';
//				num -= 5;
//			}
//		}
//		else if (10 <= num&&num<50)
//		{
//			if (num >= 40)
//			{
//				arr[i++] = 'X';
//				arr[i++] = 'L';
//				num -= 40;
//			}
//			else{
//				arr[i++] = 'X';
//				num -= 10;
//			}
//		}
//		else if (50 <= num&&num<100)
//		{
//			if (num >= 90)
//			{
//				arr[i++] = 'X';
//				arr[i++] = 'C';
//				num -= 90;
//			}
//			else{
//				arr[i++] = 'L';
//				num -= 50;
//			}
//		}
//		else if (100 <= num&&num<500)
//		{
//			if (num >= 400)
//			{
//				arr[i++] = 'C';
//				arr[i++] = 'D';
//				num -= 400;
//			}
//			else{
//				arr[i++] = 'C';
//				num -= 100;
//			}
//		}
//		else if (500 <= num&&num<1000)
//		{
//			if (num >= 900)
//			{
//				arr[i++] = 'C';
//				arr[i++] = 'M';
//				num -= 900;
//			}
//			else{
//				arr[i++] = 'D';
//				num -= 500;
//			}
//		}
//		else{
//			arr[i++] = 'M';
//			num -= 1000;
//		}
//	}
//	arr[i] = '\0';
//	return arr;
//}
//int main()
//{
//	int a = 3;
//	char *arr=intToRoman(a);
//	printf("%s", arr);
//	return 0;
//}


////42. 接雨水
//int trap(int* height, int heightSize)
//{
//	int i = 0;
//	int left = 0, right = 0;
//	int sum = 0;
//	for (i = 0; i<heightSize; i++)
//	{
//		if (i>0 && height[i] == 0 && i<heightSize - 1)
//		{
//			left = i - 1;
//			right = i + 1;
//			while (1)
//			{
//				sum += height[left]<height[right] ? height[left] : height[right];
//				if (left >= 0 && right <= heightSize - 1)
//				{
//					left--; right++;
//				}
//				if (height[left]<height[left + 1] || height[right + 1]<height[right])
//				{
//					break;
//				}
//			}
//
//		}
//	}
//	return sum;
//}
//int main()
//{
//	int height[] = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
//	int sz = sizeof(height) / sizeof(height[0]);
//	trap(height,sz);
//	return 0;
//}

////206. 反转链表
////给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
////输入：head = [1, 2, 3, 4, 5]
////输出：[5, 4, 3, 2, 1]
////方法1：原地翻转链表关系，需要三个变量
////过程：例如，1->	2->	3->	4->	5->	NULL
////NULL<-1   2->	3->	4->	5->	NULL
////NULL<-1<- 2	3->	4->	5->	NULL
////......
////NULL <- 1 <- 2 <- 3 <- 4 <- 5
//struct ListNode {
//    int val;
//     struct ListNode *next;
//};
//struct ListNode* reverseList(struct ListNode* head){
//	if (head == NULL)
//		return NULL;
//	//三个变量具体关系如下：
//	//原链表样式：	1->	2->	3->	4->	5->	NULL
//	//具体过程
//	//pre		cur		Next
//	//NULL		1		2
//	struct ListNode* pre = NULL;
//	struct ListNode* cur = head;
//	struct ListNode* Next = head->next;
//	while (cur)
//	{
//		cur->next = pre;
//		pre = cur;
//		cur = Next;
//		if (Next != NULL)
//		{
//			Next = Next->next;
//		}
//
//	}
//	return pre;
//}
////方法2：运用链表头插的方式，新建一个链表，把原链表的数据从第一个开始头插进新链表
////过程：例如，1->	2->	3->	4->	5->	NULL
////1->NULL
////2->1->NULL
////.....,最终
////5->4->3->2->1->NULL
//struct ListNode* reverseList(struct ListNode* head){
//	if (head == NULL)
//		return NULL;
//	struct ListNode* rhead = NULL;
//	struct ListNode* cur = head;
//	struct ListNode* Next = head->next;
//	//cur若指向了初始链表的最后一位NULL则退出循环
//	while (cur)
//	{
//		cur->next = rhead;
//		rhead = cur;
//		cur = Next;
//		//为防止Next超出范围，要加以限制
//		if (Next != NULL)
//			Next = Next->next;
//	}
//	return rhead;
//}

////58. 最后一个单词的长度
////给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。
////单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。
//int lengthOfLastWord(char * s)
//{
//	int i = 0;
//	//先找到最后位置
//	while (s[i] != '\0')
//	{
//		i++;
//	}
//	//-1对应倒数元素的下标
//	i--;
//	//防止最后一个元素是空格而不是单词
//	while (s[i] == ' ')
//	{
//		i--;
//	}
//	//记录单词数量
//	int sum = 0;
//	while (s[i] != ' ')
//	{
//		i--;
//		sum++;
//		//若某次i小于0了，则说明只有一个单词，为了防止数组越界，要break结束循环
//		if (i<0)
//		{
//			break;
//		}
//	}
//	return sum;
//}


//14. 最长公共前缀
//编写一个函数来查找字符串数组中的最长公共前缀。
//如果不存在公共前缀，返回空字符串 ""。
//由于此方法需要用二维数组接收，与题目要求不符，故放弃
//char * longestCommonPrefix(char ** strs, int strsSize)
//{
//	if (strsSize == 0)
//	{
//		return NULL;
//	}
//	int i = 0;
//	int j = 0;
//	char same = strs[0][0];//会报错，需要接收参数时用二维数组char strs[3][6]接收
//	int time = 0;
//	int len = strlen(strs[0]);
//	char* ret = (char*)malloc(sizeof(char)*len);
//	while (1)
//	{
//		if (strs[i][j] == same)
//		{
//			i++;
//			time++;
//		}
//		else
//		{
//			break;
//		}
//		if (time == strsSize&&i == strsSize - 1)
//		{
//			len++;
//			time = 0;
//			j++;
//			i = 0;
//			same = strs[i][j];
//		}
//	}
//	return ret;
//}
////新方法
//char* longestCommonPrefix(char** strs, int strsSize) {
//	if (strsSize <= 0) {
//		return NULL;  // 无字符串或无效输入
//	}
//
//	int len = strlen(strs[0]);  // 获取第一个字符串的长度
//	//直接用第一个字符串的长度来创建我们要返回的字符串最大的大小
//	char* ret = (char*)malloc(sizeof(char) * (len + 1));  // 分配足够的内存，+1是为了放\0
//
//	for (int j = 0; j < len; j++)
//	{
//		//每次获取strs中第一个字符串的字符，与后面进行比较
//		char same = strs[0][j];
//		//排查不同的
//		for (int i = 1; i < strsSize; i++) 
//		{
//			if (strs[i][j] != same || j >= strlen(strs[i])) 
//			{
//				ret[j] = '\0';  // 遇到不相同的字符或字符串排查结束，设置前缀结束
//				return ret;
//			}
//		}
//		//若当前字符与后续的字符串中位置字符相同，则把这个字符放进ret
//		ret[j] = same;
//	}
//	//若上述循环能出来，则说明第一个字符串就是所以我们要返回的，在len下标处放个\0返回
//	ret[len] = '\0';  // 最终的前缀以 null 结尾
//	return ret;
//}
//int main()
//{
//	char strs[3][6] = { "flower", "flow", "flight" };
//	longestCommonPrefix(strs, 3);
//	return 0;
//}


////24.反转链表
////定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点
////头插实现（链表重新头插一遍，会反转节点位置，尾插不会改变链表顺序）
//struct ListNode* reverseList(struct ListNode* head)
//{
//	if (head == NULL)
//	{
//		return NULL;
//	}
//	struct ListNode* rhead = NULL;
//	struct ListNode* cur = head;
//	struct ListNode* Next = head->next;
//	while (cur)
//	{
//		cur->next = rhead;
//		rhead = cur;
//		cur = Next;
//		if (Next != NULL)
//			Next = Next->next;
//	}
//	return rhead;
//}


////22. 链表中倒数第k个节点
////输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
////例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
////双指针（快慢指针）
////指向倒数第k个节点，就是要指向从头开始，指向总长度-k的节点，由于我们无法知道链表总长度，就只能用快慢指针实现从后往前数的效果
//struct ListNode* getKthFromEnd(struct ListNode* head, int k)
//{
//	struct ListNode* fast = head;
//	struct ListNode* low = head;
//
//	while (k)
//	{
//		fast = fast->next;
//		k--;
//	}
//
//	while (fast)
//	{
//		fast = fast->next;
//		low = low->next;
//	}
//	return low;
//}


////151. 反转字符串中的单词
////给你一个字符串 s ，请你反转字符串中 单词 的顺序。
////单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
////返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。
////注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。
//void reverse(int i, int j, char *arr)
//{
//	while (i<j)
//	{
//		char tmp = arr[i];
//		arr[i] = arr[j];
//		arr[j] = tmp;
//		i++; j--;
//	}
//}
//char * reverseWords(char * s)
//{
//	//先计算整体大小
//	int sz = strlen(s);
//	//开辟空间，存放符合要求的字符串（即开头、结尾没有空格，中间的空格不超过1个）
//	char* ret = (char*)malloc(sizeof(char)*sz + 2);//多开辟一个空间,存放\0
//	int k = 0;//我们开辟的空间的下标
//	int i = 0;//s开始的下标
//	int j = sz - 1;//s末尾的下标
//	//除去开头的空格，让i指向开头不为空格的字符
//	while (1)
//	{
//		if (s[i] == ' ')
//		{
//			i++;
//		}
//		else
//			break;
//	}
//	//除去结尾空格，从尾开始，向前遍历，找到不是空格的位置
//	while (1)
//	{
//		if (s[j] == ' ')
//		{
//			j--;
//		}
//		else
//			break;
//	}
//	//把从i开始到j结束的区域内的字符串，传给ret
//	while (i <= j)
//	{
//		//如果中间出现多个空格，则i++往后走，k不变
//		if (s[i] == ' '&&s[i + 1] == ' ')
//		{
//			i++;
//			continue;
//		}
//		ret[k++] = s[i++];
//	}
//	//复制完成之后，ret没有\0，要自己加一个
//	ret[k] = '\0';
//
//	int len = strlen(ret);//ret的长度
//	reverse(0, len - 1, ret);//翻转ret内所有字符
//	//i、j继续使用，用于后面检测每个单词
//	i = 0;
//	j = 0;
//
//	while (i<len&&j<len)
//	{
//		//不为空格，j往后走
//		if (ret[j] != ' ')
//		{
//			j++;
//		}
//		else
//		{
//			//遇到空格了，翻转空格之前的字符串
//			reverse(i, j - 1, ret);
//			i = j + 1;//i的位置重新选择到j+1（空格后的单词首字符）
//			j++;//j继续走
//		}
//	}
//	//上述循环结束后，只会剩下最后一个单词，翻转最后一个单词结束
//	reverse(i, j - 1, ret);
//	return ret;
//}
////测试
//#include<string.h>
//int main()
//{
//	char* arr = "  abc \0def  \0\0";
//	int sz = strlen(arr);
//	printf("%d", sz);
//	return 0;
//}


////28. 找出字符串中第一个匹配项的下标
////给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 - 1
////暴力解法，时间复杂度O(N*M)
//int strStr(char * haystack, char * needle)
//{
//	int len1 = strlen(haystack);
//	int len2 = strlen(needle);
//	if (len1 == len2&&len1 == 1)
//	{
//		return 0;
//	}
//	if (len2>len1)
//	{
//		return -1;
//	}
//	int i = 0, j = 0, k = 0;
//	int time = 0;
//	for (i = 0; i<len1; i++)
//	{
//		int k = i;
//		time = 0;
//		for (j = 0; j<len2; j++)
//		{
//			if (haystack[k] == needle[j])
//			{
//				time++;
//				k++;
//			}
//			else
//			{
//				break;
//			}
//			if (time == len2)
//			{
//				return i;
//			}
//		}
//	}
//	return -1;
//}


////21、合并两个有序链表
////将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
////尾插实现
//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
//{
//	//特殊情况
//	if (list1 == NULL&&list2 == NULL)
//	{
//		return NULL;
//	}
//	else if (list1 == NULL&&list2 != NULL)
//	{
//		return list2;
//	}
//	else if (list2 == NULL&&list1 != NULL)
//	{
//		return list1;
//	}
//	//正常情况
//	//控制1链表
//	struct ListNode* cur1 = list1;
//	struct ListNode* next1 = list1->next;
//	//控制2链表
//	struct ListNode* cur2 = list2;
//	struct ListNode* next2 = list2->next;
//	//rhead作为我们要返回的新链表头，cur为创建链表时，控制新链表的值
//	struct ListNode* rhead = NULL;
//	struct ListNode* cur = NULL;
//	//先找出两个链表的最小值，放到rhead和cur中
//	if (cur1->val>cur2->val)
//	{
//		rhead = cur2;
//		cur2 = next2;
//		if (next2 != NULL)
//			next2 = next2->next;
//	}
//	else
//	{
//		rhead = cur1;
//		cur1 = next1;
//		if (next1 != NULL)
//			next1 = next1->next;
//	}
//	cur = rhead;
//	//开始遍历两个链表，直到某个链表到NULL则结束
//	while (cur1 != NULL&&cur2 != NULL)
//	{
//		if (cur1->val<cur2->val)
//		{
//			cur->next = cur1;
//			cur = cur1;
//			cur1 = next1;
//			if (next1 != NULL)
//				next1 = next1->next;
//		}
//		else
//		{
//			cur->next = cur2;
//			cur = cur2;
//			cur2 = next2;
//			if (next2 != NULL)
//				next2 = next2->next;
//		}
//	}
//	//两种情况：一个遍历完，另一个肯定是还有余的，把剩下的直接排进去
//	if (cur1 != NULL)
//	{
//		while (cur1)
//		{
//			cur->next = cur1;
//			cur = cur1;
//			cur1 = next1;
//			if (next1 != NULL)
//				next1 = next1->next;
//		}
//	}
//	else if (cur2 != NULL)
//	{
//		while (cur2)
//		{
//			cur->next = cur2;
//			cur = cur2;
//			cur2 = next2;
//			if (next2 != NULL)
//				next2 = next2->next;
//		}
//	}
//	return rhead;
//}


////125. 验证回文串
////如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
////字母和数字都属于字母数字字符。
////给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。
////双指针实现
//bool isPalindrome(char * s)
//{
//	int len = strlen(s);
//	int i = 0;
//	int j = len - 1;
//	while (i <= j)
//	{
//		if (s[i] >= 'A'&&s[i] <= 'Z')
//		{
//			s[i] = s[i] + 32;
//		}
//		if (s[j] >= 'A'&&s[j] <= 'Z')
//		{
//			s[j] = s[j] + 32;
//		}
//		if (s[i]<'0' || (s[i]>'9'&&s[i]<'A') || (s[i]>'Z'&&s[i]<'a') || s[i]>'z')
//		{
//			i++;
//			continue;
//		}
//		if (s[j]<'0' || (s[j]>'9'&&s[j]<'A') || (s[j]>'Z'&&s[j]<'a') || s[j]>'z')
//		{
//			j--;
//			continue;
//		}
//		if (s[i] != s[j])
//		{
//			return false;
//		}
//		else if (s[i] == s[j])
//		{
//			i++; j--;
//		}
//	}
//	return true;
//}
//int main()
//{
//	char* s = "A man, a plan, a canal: Panama";
//	isPalindrome(s);
//	return 0;
//}


////392. 判断子序列
////给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
////字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
////双指针
//bool isSubsequence(char * s, char * t){
//	int i = 0;
//	int j = 0;
//	int len_s = strlen(s);
//	int len_t = strlen(t);
//	//子字符串为空
//	if (len_s == 0)
//	{
//		return true;
//	}
//	while (i<len_t)
//	{
//		if (s[j] == t[i])
//		{
//			j++; i++;
//		}
//		else
//		{
//			i++;
//		}
//		//j指向了子字符串的\0的位置
//		if (j == len_s)
//		{
//			return true;
//		}
//	}
//	return false;
//}


////思考全局变量和数组传参传的是什么
//int abc[10] = {0};
//void text(int abc[10])
//{
//	//因为我们传进text的abc不是整个数组，而是数组的首元素地址，而在函数内进行sizeof（abc）计算的不是数组整体的大小，而是abc这个指针的大小
//	printf("%d\n", sizeof(abc));//4
//	printf("%d\n", sizeof(abc) / sizeof(abc[0]));//1，这里的sizeof（abc）计算的是指针，由于是32位，所以是4。sizeof(abc[0])是求abc[0]这个元素的类型大小，int类型大小为4。
//}
//int main()
//{
//	//text(abc);
//	//printf("%d\n", sizeof(abc));//40
//	int a = 9;
//	printf("%02d", a);
//	return 0;
//}


//167. 两数之和 II - 输入有序数组
//给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列  ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
//以长度为 2 的整数数组[index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
//你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
//你所设计的解决方案必须只使用常量级的额外空间。
int* twoSum(int* numbers, int numbersSize, int target, int* returnSize)
{
	int* ret = (int*)malloc(sizeof(int) * 2);
	int i = 0, j = 0;
	int flag = 0;
	for (i = 0; i<numbersSize; i++)
	{

		for (j = i + 1; j<numbersSize; j++)
		{
			if (target - numbers[i] == numbers[j])
			{
				flag = 1;
				break;
			}
		}
		if (flag == 1)
		{
			break;
		}
	}
	ret[0] = i + 1;
	ret[1] = j + 1;
	*returnSize = 2;
	return ret;
}


////强迫症
////小强在统计一个小区里居民的出生年月，但是发现大家填写的生日格式不统一，例如有的人写 199808，有的人只写 9808。有强迫症的小强请你写个程序，把所有人的出生年月都整理成 年年年年 - 月月 格式。对于那些只写了年份后两位的信息，我们默认小于 22 都是 20 开头的，其他都是 19 开头的。
////输入格式：
////输入在一行中给出一个出生年月，为一个 6 位或者 4 位数，题目保证是 1000 年 1 月到 2021 年 12 月之间的合法年月。
////输出格式：
////在一行中按标准格式 年年年年 - 月月 将输入的信息整理输出。
//int main()
//{
//	int input;
//	int month;
//	int year;
//	scanf("%d", &input);
//	if (input<10000)
//	{
//		month = input % 100;
//		year = input / 100;
//		if (year<22)
//		{
//			year += 2000;
//			printf("%d-%02d", year, month);
//		}
//		else{
//			year += 1900;
//			printf("%d-%02d", year, month);
//		}
//	}
//	else{
//		month = input % 100;
//		year = input / 100;
//		printf("%d-%02d", year, month);
//	}
//	return 0;
//}


////7 - 2 幸运彩票
////彩票的号码有 6 位数字，若一张彩票的前 3 位上的数之和等于后 3 位上的数之和，则称这张彩票是幸运的。本题就请你判断给定的彩票是不是幸运的。
////输入格式：
////输入在第一行中给出一个正整数 N（≤ 100）。随后 N 行，每行给出一张彩票的 6 位数字。
////输出格式：
////对每张彩票，如果它是幸运的，就在一行中输出 You are lucky!；否则输出 Wish you good luck.。
//int main()
//{
//	int number;
//	scanf("%d", &number);
//	int *input = (int*)malloc(sizeof(int)*number);
//	int i = 0, t = number;
//	while (number--)
//	{
//		scanf("%d", &input[i++]);
//	}
//	for (i = 0; i<t; i++)
//	{
//		int qian, hou, sum_qian = 0, sum_hou = 0;
//		hou = input[i] % 1000;
//		qian = input[i] / 1000;
//		while (hou)
//		{
//			sum_hou += hou % 10;
//			hou /= 10;
//		}
//		while (qian)
//		{
//			sum_qian += qian % 10;
//			qian /= 10;
//		}
//		if (sum_hou == sum_qian)
//		{
//			printf("You are lucky!\n");
//		}
//		else{
//			printf("Wish you good luck.\n");
//		}
//	}
//	return 0;
//}


////7 - 3 编程团体赛
////编程团体赛的规则为：每个参赛队由若干队员组成；所有队员独立比赛；参赛队的成绩为所有队员的成绩和；成绩最高的队获胜。
////现给定所有队员的比赛成绩，请你编写程序找出冠军队。
////输入格式：
////输入第一行给出一个正整数 N（≤104），即所有参赛队员总数。随后 N 行，每行给出一位队员的成绩，格式为：队伍编号 - 队员编号 成绩，其中队伍编号为 1 到 1000 的正整数，队员编号为 1 到 10 的正整数，成绩为 0 到 100 的整数。
//int main()
//{
//	int number;
//	scanf("%d", &number);
//	int* team = (int*)malloc(sizeof(int)*number);
//	int* s = (int*)malloc(sizeof(int)*number);
//	int n, t = number;
//	int i = 0;
//	while (number--)
//	{
//		scanf("%d-%d %d", &team[i], &n, &s[i]); i++;
//	}
//	int sorce[1001] = { 0 };
//	for (i = 0; i<t; i++)
//	{
//		sorce[team[i]] += s[i];
//	}
//
//	int max = 0;
//	for (i = 0; i<1001; i++)
//	{
//		max = max>sorce[i] ? max : sorce[i];
//	}
//	for (i = 0; i<1001; i++)
//	{
//		if (sorce[i] == max)
//		{
//			break;
//		}
//	}
//	printf("%d %d", i, max);
//	return 0;
//}


//11. 盛最多水的容器
//给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是(i, 0) 和(i, height[i]) 。
//找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
//返回容器可以储存的最大水量。
//说明：你不能倾斜容器。
//双指针，左右取
//分析：由于储水量=下标距离*两个元素的最低值，所以我们刚开始可以从两边开始遍历，当检测到小的那部分，就移动一位，并且算出移动前的储水量
int maxArea(int* height, int heightSize)
{
	int i = 0;
	int j = heightSize - 1;
	int water = 0;//返回的最大储水量
	int litter = 0;//暂时存放左右遍历的较小值
	int sum = 0;//存放零时储水量
	while (i<j)
	{
		//找到两边的最小值
		if (height[i]<height[j])
		{
			litter = height[i++];
		}
		else
		{
			litter = height[j--];
		}
		//计算当前两个元素的储水量
		sum = litter*(j - i + 1);
		//每次的储水量都与前一次进行比较，取较大的一次
		if (sum>water)
		{
			water = sum;
		}
	}
	return water;
}


//42.接雨水
//给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水
////时间复杂为O(M*N) 超了
//int trap(int* height, int heightSize)
//{
//	int sum = 0;
//	int max = 0;
//	int i = 0;
//	for (i = 0; i<heightSize; i++)
//	{
//		if (max<height[i])
//		{
//			max = height[i];
//		}
//	}
//	int first = 1;
//	i = 0;
//	int j = heightSize - 1;
//	while (first <= max)
//	{
//		while (height[i]<first)
//		{
//			i++;
//		}
//		while (height[j]<first)
//		{
//			j--;
//		}
//		if (i == j)
//		{
//			break;
//		}
//		int k = i;
//		while (k <= j)
//		{
//			if (height[k]<first)
//			{
//				sum++; k++;
//			}
//			else
//			{
//				k++;
//			}
//		}
//		first++;
//	}
//	return sum;
//}
////时间复杂度O(N)，空间复杂度O(N)
////创建左右两个数组，分别存储从左看和从右看的取高部分
//int trap(int* height, int heightSize)
//{
//	//存放刚开始的数组内的数字（相当于柱子）
//	int sum = 0;
//	int i = 0;
//	//计算hight的已有的数字
//	for (i = 0; i<heightSize; i++)
//	{
//		sum += height[i];
//	}
//	//定义俩个数组
//	int *left = (int*)malloc(sizeof(int)*heightSize);
//	int *right = (int*)malloc(sizeof(int)*heightSize);
//	//从左边第一个元素开始，取最大
//	int left_max = height[0];
//	for (i = 0; i<heightSize; i++)
//	{
//		//只要当前元素大于left_max，就把这个较大值赋给left_max，然后再给left数组赋予较大的值
//		if (height[i] >= left_max)
//		{
//			left_max = height[i];
//			left[i] = left_max;
//		}
//		else//若是小的，则直接把left_max赋给left
//		{
//			left[i] = left_max;
//		}
//	}
//	//right从右遍历，过程与left一样
//	int right_max = height[heightSize - 1];
//	int j = heightSize - 1;
//	for (j = heightSize - 1; j >= 0; j--)
//	{
//		if (height[j] >= right_max)
//		{
//			right_max = height[j];
//			right[j] = right_max;
//		}
//		else
//		{
//			right[j] = right_max;
//		}
//	}
//	//取left和right两个数组的重复的部分，重新赋给left，当做最后重复的部分数组
//	int k = 0;
//	for (k = 0; k<heightSize; k++)
//	{
//		if (left[k]>right[k])
//		{
//			left[k] = right[k];
//		}
//	}
//	//存放重复的部分的总大小
//	int rep_num = 0;
//	//计算重复的部分
//	for (k = 0; k<heightSize; k++)
//	{
//		rep_num += left[k];
//	}
//	//使用完释放空间
//	free(left);
//	free(right);
//	left = NULL;
//	right = NULL;
//	//返回重复的部分减去柱子的部分（原数组的大小）就得到了储水量
//	return rep_num - sum;
//}
////上述测试
//int main()
//{
//	int arr[12] = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
//	int ret=trap(arr, 12);
//	printf("%d", ret);
//	return 0;
//}


////383. 赎金信
////给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
////如果可以，返回 true ；否则返回 false 。
////magazine 中的每个字符只能在 ransomNote 中使用一次。
//#include<string.h>
//bool canConstruct(char * ransomNote, char * magazine)
//{
//	int i = 0;
//	int j = 0;
//	int len_r = strlen(ransomNote);
//	int len_m = strlen(magazine);
//	int arr[123] = { 0 };
//	int brr[123] = { 0 };
//	for (i = 0; i<len_r; i++)
//	{
//		arr[ransomNote[i]]++;
//	}
//	for (j = 0; j<len_m; j++)
//	{
//		brr[magazine[j]]++;
//	}
//	int k = 0;
//	for (k = 0; k<123; k++)
//	{
//		if (arr[k]>brr[k] && arr[k] != 0)
//		{
//			return false;
//		}
//	}
//	return true;
//}
//int main()
//{
//	char crr[] = "aa";
//	char drr[] = "abb";
//	canConstruct(crr,drr);
//	return 0;
//}
//

////两数之和
////给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
////你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
////你可以按任意顺序返回答案
//int* twoSum(int* nums, int numsSize, int target, int* returnSize)
//{
//	int i = 0;
//	int j = 0;
//	int flag = 0;
//	int* ret = (int*)malloc(sizeof(int) * 2);
//	for (i = 0; i<numsSize; i++)
//	{
//		for (j = i + 1; j<numsSize; j++)
//		{
//			if (nums[i] + nums[j] == target)
//			{
//				flag = 1;
//				break;
//			}
//		}
//		if (flag == 1)
//		{
//			break;
//		}
//	}
//	ret[0] = i;
//	ret[1] = j;
//	*returnSize = 2;
//	return ret;
//}


////同构字符串
//bool isIsomorphic(char * s, char * t)
//{
//	int len_s = strlen(s);
//	int len_t = strlen(t);
//	if (len_s != len_t)
//	{
//		return false;
//	}
//	//每种字符出现的次数要相同
//	int arr[123] = { 0 };
//	int brr[123] = { 0 };
//	for (int i = 0; i<len_s; i++)
//	{
//		arr[s[i]]++;
//		brr[t[i]]++;
//		if (arr[s[i]] != brr[t[i]])
//		{
//			return false;
//		}
//	}
//	//出现的位置也要相同
//	int j = 1;
//	while (j<len_s)
//	{
//		if (((s[j] != s[j - 1]) && (t[j] != t[j - 1])) || ((s[j] == s[j - 1]) && (t[j] == t[j - 1])))
//		{
//			j++;
//		}
//		else
//		{
//			return false;
//		}
//	}
//	return true;
//}


////141. 环形链表
////给你一个链表的头节点 head ，判断链表中是否有环。
////如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。返回true，否则返回false
//bool hasCycle(struct ListNode *head) {
//	struct ListNode *low = head;
//	struct ListNode *fast = head;
//	while (fast&&fast->next)
//	{
//		low = low->next;
//		fast = fast->next->next;
//		if (fast == low)
//		{
//			return true;
//		}
//	}
//	return false;
//}


////判断3个点能否组成三角形，能就返回周长与面积
//int main()
//{
//	double x1, y1, x2, y2, x3, y3;
//	scanf("%lf %lf %lf %lf %lf %lf", &x1, &y1, &x2, &y2, &x3, &y3);
//	double l1 = sqrt((double)((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2)));
//	double l2 = sqrt((double)((x1 - x3)*(x1 - x3) + (y1 - y3)*(y1 - y3)));
//	double l3 = sqrt((double)((x2 - x3)*(x2 - x3) + (y2 - y3)*(y2 - y3)));
//	if (l1 + l2>l3&&l1 + l3>l2&&l2 + l3>l1)
//	{
//		double c = l1 + l2 + l3;
//		double s = sqrt(c / 2 * (c / 2 - l1)*(c / 2 - l2)*(c / 2 - l3));
//		printf("L = %.2lf, A = %.2lf\n", c, s);
//	}
//	else{
//		printf("Impossible\n");
//	}
//	return 0;
//}
//
//
////判断能否进入图书馆
////输入在一行中给出 4 个整数：
////禁入年龄线 陪同年龄线 询问者1的年龄 询问者2的年龄
////这里的禁入年龄线是指严格小于该年龄的儿童禁止入馆；陪同年龄线是指大于等于该年龄的人士可以陪同儿童入馆。默认两个询问者的编号依次分别为 1 和 2；年龄和年龄线都是[1, 200] 区间内的整数，并且保证 陪同年龄线 严格大于 禁入年龄线。
//int main()
//{
//	int a, b, c, d;
//	scanf("%d %d %d %d", &a, &b, &c, &d);
//
//	if (c<a)
//	{
//		if (d<a)
//		{
//			printf("%d-N %d-N\n", c, d);
//			printf("zhang da zai lai ba\n");
//		}
//		else if (d>a&&d<b)
//		{
//			printf("%d-N %d-Y\n", c, d);
//			printf("2: huan ying ru guan\n");
//		}
//		else{
//			printf("%d-Y %d-Y\n", c, d);
//			printf("qing 2 zhao gu hao 1\n");
//		}
//	}
//	else if (c>a&&c<b)
//	{
//		if (d<a)
//		{
//			printf("%d-Y %d-N\n", c, d);
//			printf("1: huan ying ru guan\n");
//		}
//		else if (d>a&&d<b)
//		{
//			printf("%d-Y %d-Y\n", c, d);
//			printf("huan ying ru guan\n");
//		}
//		else{
//			printf("%d-Y %d-Y\n", c, d);
//			printf("huan ying ru guan\n");
//		}
//	}
//	else{
//		if (d<a)
//		{
//			printf("%d-Y %d-Y\n", c, d);
//			printf("qing 1 zhao gu hao 2\n");
//		}
//		else if (d>a&&d<b)
//		{
//			printf("%d-Y %d-Y\n", c, d);
//			printf("huan ying ru guan\n");
//		}
//		else{
//			printf("%d-Y %d-Y\n", c, d);
//			printf("huan ying ru guan\n");
//		}
//	}
//	return 0;
//}
//
//
////求一元二次方程的各种情况的根
////本题目要求一元二次方程
////ax2＋bx＋c＝0的根，结果保留2位小数。（注意：0.00会在gcc下被输出为 - 0.00，需要做特殊处理，输出正确的0.00。）
//int main()
//{
//	float a, b, c;
//	scanf("%f %f %f", &a, &b, &c);
//	if (a == b&&b == c&&c == 0)
//	{
//		printf("Zero Equation");
//		return 0;
//	}
//	if (a == b&&a == 0 && c != 0)
//	{
//		printf("Not An Equation");
//		return 0;
//	}
//	if (a == 0 && b != 0 && c != 0)
//	{
//		float x;
//		x = (-c) / b;
//		printf("%.2f\n", x);
//		return 0;
//	}
//
//	float d = b*b - 4 * a*c;
//	if (d>0)
//	{
//		float x1, x2;
//		x1 = (-b + sqrt(d)) / (2 * a);
//		x2 = (-b - sqrt(d)) / (2 * a);
//		printf("%.2f\n%.2f\n", x1, x2);
//	}
//	else if (d == 0)
//	{
//		float x;
//		x = (-b) / (2 * a);
//		printf("%.2f\n", x);
//	}
//	else{
//		float x1;
//		x1 = (-b) / (2 * a);
//		if (x1 == 0)
//		{
//			x1 *= -1;
//		}
//		float x2;
//		x2 = sqrt(-d) / (2 * a);
//		printf("%.2f+%.2fi\n", x1, x2);
//		printf("%.2f-%.2fi\n", x1, x2);
//	}
//	return 0;
//}
//
//
////计算时间是几点
////有时候人们用四位数字表示一个时间，比如 1106 表示 11 点零 6 分。现在，你的程序要根据起始时间和流逝的时间计算出终止时间。
////读入两个数字，第一个数字以这样的四位数字表示当前时间，第二个数字表示分钟数，计算当前时间经过那么多分钟后是几点，结果也表示为四位数字。当小时为个位数时，没有前导的零，例如 5 点 30 分表示为 530；0 点 30 分表示为 030。注意，第二个数字表示的分钟数可能超过 60，也可能是负数。
//int main()
//{
//	int a, b;
//	scanf("%d %d", &a, &b);
//	if (b>0)
//	{
//		int c = b / 60 * 100;
//		int d = b % 60;
//		a += c;
//		int e = a % 100;
//		a -= e;
//		e += d;
//		int f = e / 60 * 100;
//		int g = e % 60;
//		a = a + f + g;
//		printf("%d", a);
//	}
//	else{
//		b *= -1;
//		int c = b / 60 * 100;
//		int d = b % 60;
//		a -= c;
//		int e = a % 100;
//		a -= e;
//		if (e - d>0)
//		{
//			a += e - d;
//		}
//		else
//		{
//			a -= 100;
//			e += 60;
//			a += e - d;
//		}
//		if (a>100)
//		{
//			printf("%d", a);
//		}
//		else{
//			printf("%03d", a);
//		}
//	}
//	return 0;
//}

//#include <stdio.h>
//#include <math.h>
//main()
//{
//	float a, b, c;
//	double f, d, e, x, a1, a2;
//	scanf("%f%f%f", &a, &b, &c);
//	f = b*b - a*c * 4;
//	if (a != 0)
//	{
//		if (f>0)
//		{
//			d = (-b + sqrt(f)) / (2 * a);
//			e = (-b - sqrt(f)) / (2 * a);
//			printf("%0.2f\n", d);
//			printf("%0.2f", e);
//		}
//		else if (f == 0)
//		{
//			d = -b / (2 * a);
//			printf("%0.2f\n", d);
//		}
//		else
//		{
//			if (b != 0)
//			{
//				a1 = (-b) / (2 * a);
//				a2 = sqrt(-f) / (2 * a);
//				printf("%.2f+%.2lfi\n", a1, a2);
//				printf("%.2f-%.2lfi\n", a1, a2);
//			}
//			else
//			{
//				x = sqrt(-f) / (2 * a);
//				printf("%0.2f%-0.2fi\n", 0.0, x);
//				printf("%0.2f%-0.2fi", 0.0, -x);
//			}
//		}
//
//	}
//	else if (a == 0 && b == 0 && c == 0)
//		printf("Zero Equation\n");
//	else if (a == 0 && b == 0 && c != 0)
//		printf("Not An Equation\n");
//	else if (a == 0 && b != 0 && c != 0)
//		printf("%.2f\n", (-c*1.0) / b);
//}


////283. 移动零
////给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
////请注意 ，必须在不复制数组的情况下原地对数组进行操作。
//void moveZeroes(int* nums, int numsSize){
//	int i = 0, j = 0;
//	for (i = 0; i<numsSize; i++)
//	{
//		if (nums[i] == 0)
//		{
//			for (j = i + 1; j<numsSize; j++)
//			{
//				if (nums[j] != 0)
//				{
//					nums[i] = nums[j];
//					nums[j] = 0;
//					if (j == numsSize - 1)
//					{
//						return;
//					}
//					break;
//				}
//			}
//		}
//	}
//}


////面试题 17.04.消失的数字
////数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
////方法1，时间O（N）
//int missingNumber(int* nums, int numsSize){
//	int N = numsSize;
//	//求0——N之间的数字总和（没有缺失数字前的总和）
//	int sum = N*(N + 1) / 2;
//	for (int i = 0; i<numsSize; i++)
//	{
//		sum -= nums[i];
//	}
//	return sum;
//}
////方法2，时间O（N）
////类似于找单身狗
//int missingNumber(int* nums, int numsSize){
//	int N = numsSize;
//	int sum = N*(N + 1) / 2;
//	int j = 0;
//	for (int i = 0; i<numsSize; i++)
//	{
//		j ^= nums[i];
//	}
//	for (int i = 0; i <= numsSize; i++)
//	{
//		j ^= i;
//	}
//	return j;
//}


////轮转数组
////O(N)
//void reverse(int* nums, int i, int j)
//{
//	while (i<j)
//	{
//		int tmp = nums[i];
//		nums[i] = nums[j];
//		nums[j] = tmp;
//		i++; j--;
//	}
//}
//void rotate(int* nums, int numsSize, int k)
//{
//	if (numsSize>k)
//	{
//		reverse(nums, 0, numsSize - 1);
//		reverse(nums, 0, k - 1);
//		reverse(nums, k, numsSize - 1);
//	}
//	else
//	{
//		int j = k%numsSize;
//		reverse(nums, 0, numsSize - 1);
//		reverse(nums, 0, j - 1);
//		reverse(nums, j, numsSize - 1);
//
//	}
//}
////O（N^2）
//void reverse1(int* nums, int numsSize)
//{
//	int tmp = nums[numsSize - 1];
//	int i;
//	for (int i = numsSize - 1; i>0; i--)
//	{
//		nums[i] = nums[i - 1];
//	}
//	nums[0] = tmp;
//}
//void rotate(int* nums, int numsSize, int k)
//{
//	if (numsSize>k)
//	{
//		while (k)
//		{
//			reverse1(nums, numsSize);
//			k--;
//		}
//	}
//	else
//	{
//		int j = k%numsSize;
//		while (j)
//		{
//			reverse1(nums, numsSize);
//			j--;
//		}
//	}
//}


////求给定精度的简单交错序列部分和
////本题要求编写程序，计算序列部分和 1 - 1 / 4 + 1 / 7 - 1 / 10 + ... 直到最后一项的绝对值不大于给定精度eps。
//#include<stdio.h>
//int main()
//{
//	double a;
//	scanf("%lf", &a);
//	double n = 1;
//	double s = 0;
//	double sum = 0;
//	s = 1.0 / n;
//	int flag = 1;
//	do
//	{
//		sum = flag*s + sum;
//		n += 3;
//		flag *= -1;
//		s = 1.0 / n;
//	} while (s >= a);
//	printf("sum = %.6lf", sum);
//	return 0;
//}

////约分最简分式
////分数可以表示为分子 / 分母的形式。编写一个程序，要求用户输入一个分数，然后将其约分为最简分式。最简分式是指分子和分母不具有可以约分的成分了。
////如6 / 12可以被约分为1 / 2。当分子大于分母时，不需要表达为整数又分数的形式，即11 / 8还是11 / 8；而当分子分母相等时，仍然表达为1 / 1的分数形式
//#include<stdio.h>
//int main()
//{
//	int a, b;
//	scanf("%d/%d", &a, &b);
//	if (a>b)
//		printf("%d/%d", a, b);
//	else if (a == b)
//		printf("1/1");
//	else{
//		int c = 0;
//		int a1 = a, b1 = b;
//		while (c = a1%b1)
//		{
//			a1 = b1;
//			b1 = c;
//		}
//		a /= b1;
//		b /= b1;
//		printf("%d/%d", a, b);
//	}
//	return 0;
//}
//
//
//void swap(int* nums, int i, int numsSize)
//{
//	int j = i + 1;
//	while (j<numsSize)
//	{
//		nums[i++] = nums[j++];
//	}
//}
//int removeDuplicates(int* nums, int numsSize)
//{
//	int n = ;
//	int dest = 0;
//	int str = 1;
//	while (str<numsSize - 1)
//	{
//		if (nums[str] == nums[dest])
//		{
//			swap(nums, dest, numsSize);
//		}
//		else
//		{
//			str++; dest++; n++;
//		}
//	}
//	return n;
//}

////合并两个数组（变长数组和创建额外数组的方式实现）
//void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
//{
//	int tmp[nums1Size];
//	int i = 0, j = 0, k = 0;
//	while (i<m&&j<n)
//	{
//		if (nums1[i] <= nums2[j])
//		{
//			tmp[k] = nums1[i];
//			i++;
//		}
//		else
//		{
//			tmp[k] = nums2[j];
//			j++;
//		}
//		k++;
//	}
//
//	while (j<n)
//	{
//		tmp[k] = nums2[j];
//		k++; j++;
//	}
//	while (i<m)
//	{
//		tmp[k] = nums1[i];
//		k++; i++;
//	}
//	for (int x = 0; x<nums1Size; x++)
//	{
//		nums1[x] = tmp[x];
//	}
//}


////203. 移除链表元素
////给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
///**
//* Definition for singly-linked list.
//* struct ListNode {
//*     int val;
//*     struct ListNode *next;
//* };
//*/
//struct ListNode* removeElements(struct ListNode* head, int val) {
//	struct ListNode* cur = head;
//	struct ListNode* prev = NULL;
//	while (cur)
//	{
//		if (cur->val == val)
//		{
//			//如果是首节点，则进行头删
//			if (cur == head)
//			{
//				prev = cur;
//				cur = cur->next;
//				free(prev);
//				head = cur;
//			}
//			else
//			{
//				prev->next = cur->next;
//				free(cur);
//				cur = prev->next;
//			}
//		}
//		else{
//			prev = cur;
//			cur = cur->next;
//		}
//	}
//	return head;
//}
//
//
////876. 链表的中间结点
////给你单链表的头结点 head ，请你找出并返回链表的中间结点。
////如果有两个中间结点，则返回第二个中间结点。
///**
//* Definition for singly-linked list.
//* struct ListNode {
//*     int val;
//*     struct ListNode *next;
//* };
//*/
//struct ListNode* middleNode(struct ListNode* head) {
//	int sum = 0;
//	struct ListNode* cur = head;
//	struct ListNode* now = head;
//	while (cur)
//	{
//		sum++;
//		cur = cur->next;
//	}
//	sum /= 2;
//	while (sum--)
//	{
//		now = now->next;
//	}
//	head = now;
//	return now;
//}
//
//
////链表中倒数第k个结点
////输入一个链表，输出该链表中倒数第k个结点。
//struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) {
//	// write code here
//	struct ListNode* fast = pListHead;
//	struct ListNode* slow = pListHead;
//	while (k--)
//	{
//		if (fast == NULL)
//			return NULL;
//		fast = fast->next;
//	}
//	while (fast)
//	{
//		fast = fast->next;
//		slow = slow->next;
//	}
//	return slow;
//}
//
//
////160. 相交链表
////给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
///**
//* Definition for singly-linked list.
//* struct ListNode {
//*     int val;
//*     struct ListNode *next;
//* };
//*/
//struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
//	struct ListNode *first1 = headA;
//	struct ListNode *first2 = headB;
//	int sum1 = 1, sum2 = 1;
//	while (first1->next)
//	{
//		first1 = first1->next;
//		sum1++;
//	}
//	while (first2->next)
//	{
//		first2 = first2->next;
//		sum2++;
//	}
//	if (first1 == first2)
//	{
//		struct ListNode *s1 = headA;
//		struct ListNode *s2 = headB;
//		if (sum1>sum2)
//		{
//			int c = sum1 - sum2;
//			while (c--)
//			{
//				s1 = s1->next;
//			}
//			while (s1 != s2)
//			{
//				s1 = s1->next;
//				s2 = s2->next;
//			}
//			return s1;
//		}
//		else if (sum1<sum2)
//		{
//			int c = sum2 - sum1;
//			while (c--)
//			{
//				s2 = s2->next;
//			}
//			while (s1 != s2)
//			{
//				s1 = s1->next;
//				s2 = s2->next;
//			}
//			return s1;
//		}
//		else{
//			while (s1 != s2)
//			{
//				s1 = s1->next;
//				s2 = s2->next;
//			}
//			return s1;
//		}
//	}
//	else
//		return NULL;
//}
//
//
////141. 环形链表
////给你一个链表的头节点 head ，判断链表中是否有环。
////如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
////为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
////如果链表中存在环 ，则返回 true 。 否则，返回 false 。
///**
//* Definition for singly-linked list.
//* struct ListNode {
//*     int val;
//*     struct ListNode *next;
//* };
//*/
//bool hasCycle(struct ListNode *head) {
//	struct ListNode *fast = head;
//	struct ListNode *slow = head; \
//		int i = 0;
//	while (fast != NULL&&slow != NULL)
//	{
//		for (i = 0; i<2; i++)
//		{
//			fast = fast->next;
//			if (fast == NULL)
//			{
//				return false;
//			}
//		}
//		slow = slow->next;
//		if (slow == fast)
//			return true;
//	}
//	//若原链表为空，则也返回false
//	return false;
//}
//
//
////142. 环形链表 II
////给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
////如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 
////为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
////如果 pos 是 - 1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
////不允许修改 链表。
///**
//* Definition for singly-linked list.
//* struct ListNode {
//*     int val;
//*     struct ListNode *next;
//* };
//*/
//struct ListNode *detectCycle(struct ListNode *head) {
//	struct ListNode *slow = head;
//	struct ListNode *fast = head;
//	while (fast&&fast->next)
//	{
//		slow = slow->next;
//		fast = fast->next->next;
//		if (fast == slow)
//		{
//			struct ListNode *meet = slow;
//			struct ListNode *newhead = head;
//			while (meet != newhead)
//			{
//				meet = meet->next;
//				newhead = newhead->next;
//			}
//			return newhead;
//		}
//	}
//	return NULL;
//}
//
//
////138. 随机链表的复制
///**
//* Definition for a Node.
//* struct Node {
//*     int val;
//*     struct Node *next;
//*     struct Node *random;
//* };
//*/
//struct Node* copyRandomList(struct Node* head) {
//	struct Node* cur = head;
//	//拷贝前一个节点
//	while (cur)
//	{
//		struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
//		copy->val = cur->val;
//		copy->next = cur->next;
//		cur->next = copy;
//		cur = cur->next->next;
//	}
//	//连上random
//	cur = head;
//	while (cur)
//	{
//		struct Node* copy = cur->next;
//		if (cur->random == NULL)
//		{
//			copy->random = NULL;
//		}
//		else
//		{
//			copy->random = cur->random->next;
//		}
//		cur = cur->next->next;
//	}
//	//分离出额外插入的部分，进行尾插
//	cur = head;
//	struct Node* newhead = NULL;
//	struct Node* tail = NULL;//控制newhead链接
//	while (cur)
//	{
//		struct Node* copy = cur->next;
//		if (newhead == NULL)
//		{
//			newhead = tail = copy;
//		}
//		else{
//			tail->next = cur->next;
//			tail = tail->next;
//		}
//		cur = cur->next->next;
//	}
//	return newhead;
//
//}


////20. 有效的括号
////给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
////有效字符串需满足：
////左括号必须用相同类型的右括号闭合。
////左括号必须以正确的顺序闭合。
////每个右括号都有一个对应的相同类型的左括号。
////用栈实现
//#include<assert.h>
//typedef char stacktype;
//typedef struct Stack
//{
//	stacktype *val;
//	int top;
//}Stack;
////出栈
//void StackPop(Stack* phead)
//{
//	assert(phead);
//	assert(phead->top > -1);
//	phead->top--;
//}
////栈初始化
//void StackInit(Stack* phead)
//{
//	assert(phead);
//	phead->top = -1;
//	phead->val = NULL;
//}
////入栈
//void StackPush(Stack* phead, stacktype x)
//{
//	assert(phead);
//	phead->val[phead->top + 1] = x;
//	phead->top++;
//}
////检测栈是否为空,空为1，非空为0
//int StackEmpty(Stack* phead)
//{
//	assert(phead);
//
//	if (phead->top == -1)
//		return 1;
//	else
//		return 0;
//}
////获取栈顶元素
//stacktype StackTop(Stack* phead)
//{
//	assert(phead);
//	assert(phead->top > -1);
//	return phead->val[phead->top];
//}
//
//bool isValid(char* s) {
//	int sz = strlen(s);
//	Stack pl;
//	StackInit(&pl);
//	stacktype* arr = (stacktype*)malloc(sizeof(char)*sz);
//	pl.val = arr;
//	for (int i = 0; i<sz; i++)
//	{
//		if (s[i] == '{' || s[i] == '[' || s[i] == '(')
//		{
//			StackPush(&pl, s[i]);
//		}
//		else
//		{
//			if (!StackEmpty(&pl))
//			{
//				if (s[i] == '}')
//				{
//					if (StackTop(&pl) == '{')
//						StackPop(&pl);
//					else{
//						return false;
//					}
//				}
//				else if (s[i] == ']')
//				{
//					if (StackTop(&pl) == '[')
//						StackPop(&pl);
//					else{
//						return false;
//					}
//				}
//				else{
//					if (StackTop(&pl) == '(')
//						StackPop(&pl);
//					else{
//						return false;
//					}
//				}
//			}
//			else
//				return false;
//		}
//	}
//	if (!StackEmpty(&pl))
//		return false;
//	return true;
//}
//int main()
//{
//	char* brr= "()";
//	isValid(brr);
//	//char* crr = NULL;
//	//crr = malloc(sizeof(char) * 2);
//	//for (int i = 0; i < 2; i++)
//	//	crr[i] = brr[i];
//	return 0;
//}



////用队列实现栈
//#include<assert.h>
//typedef struct QueueNode
//{
//	struct QueueNode* next;
//	int val;
//}QNode;
//typedef struct Queue
//{
//	QNode* front;
//	QNode* tail;
//	int size;
//}Queue;
//
////初始化队列
//void QueueInit(Queue* phead)
//{
//	assert(phead);
//	phead->front = NULL;
//	phead->tail = NULL;
//	phead->size = 0;
//}
////尾部入列
//void Queuepush(Queue* phead, int x)
//{
//	assert(phead);
//	QNode* NewNode = (QNode*)malloc(sizeof(QNode));
//	if (NewNode == NULL)
//	{
//		perror("malloc");
//		exit(-1);
//	}
//	NewNode->val = x;
//	NewNode->next = NULL;
//	//没有元素
//	if (phead->front == NULL)
//	{
//		phead->front = NewNode;
//		phead->tail = NewNode;
//	}
//	else
//	{
//		phead->tail->next = NewNode;
//		phead->tail = phead->tail->next;
//	}
//	phead->size++;
//}
////判断队列是否为空,空为1，非空为0
//int QueueEmpty(Queue* phead)
//{
//	assert(phead);
//	if (phead->front == NULL)
//		return 1;
//	else
//		return 0;
//}
////头部出列
//void Queuepop(Queue* phead)
//{
//	assert(phead);
//	assert(phead->front);
//
//	QNode* oldhead = phead->front;
//	phead->front = phead->front->next;
//	free(oldhead);
//	oldhead = NULL;
//
//	//如果删到最后一个元素，可能导致tail出现野指针
//	if (phead->front == NULL)
//		phead->tail = NULL;
//	phead->size--;
//}
////查看尾部元素
//int Queuetail(Queue* phead)
//{
//	assert(phead);
//	assert(phead->front);
//	return phead->tail->val;
//}
////查看头部元素
//int Queuetop(Queue* phead)
//{
//	assert(phead);
//	assert(phead->front);
//	return phead->front->val;
//}
////查看队列中已有的元素个数
//int QueueSize(Queue* phead)
//{
//	assert(phead);
//	return phead->size;
//}
////销毁队列
//void QueueDestory(Queue* phead)
//{
//	assert(phead);
//	QNode* cur = phead->front;
//	while (cur)
//	{
//		phead->front = phead->front->next;
//		free(cur);
//		cur = phead->front;
//	}
//	phead->front = phead->tail = NULL;
//	phead->size = 0;
//}
//
///////
//typedef struct {
//	Queue s1;
//	Queue s2;
//} MyStack;
//
//MyStack* myStackCreate() {
//	MyStack* qs = (MyStack*)malloc(sizeof(MyStack));
//	QueueInit(&qs->s1);
//	QueueInit(&qs->s2);
//	return qs;
//}
//
//void myStackPush(MyStack* obj, int x) {
//	if (!QueueEmpty(&obj->s1))
//		Queuepush(&obj->s1, x);
//	else
//		Queuepush(&obj->s2, x);
//}
//
//int myStackPop(MyStack* obj) {
//	int ret;
//	if (!QueueEmpty(&obj->s1))
//	{
//		while (QueueSize(&obj->s1)>1)
//		{
//			ret = Queuetop(&obj->s1);
//			Queuepush(&obj->s2, ret);
//			Queuepop(&obj->s1);
//		}
//		ret = Queuetop(&obj->s1);
//		Queuepop(&obj->s1);
//	}
//	else{
//		while (QueueSize(&obj->s2)>1)
//		{
//			ret = Queuetop(&obj->s2);
//			Queuepush(&obj->s1, ret);
//			Queuepop(&obj->s2);
//		}
//		ret = Queuetop(&obj->s2);
//		Queuepop(&obj->s2);
//	}
//	return ret;
//}
//
//int myStackTop(MyStack* obj) {
//	if (!QueueEmpty(&obj->s1))
//	{
//		return Queuetail(&obj->s1);
//	}
//	else{
//		return Queuetail(&obj->s2);
//	}
//}
//
//int myStackEmpty(MyStack* obj) {
//	return QueueEmpty(&obj->s1) && QueueEmpty(&obj->s2);
//}
//
//void myStackFree(MyStack* obj) {
//	QueueDestory(&obj->s1);
//	QueueDestory(&obj->s2);
//	free(obj);
//}
//
//int main()
//{
//	MyStack* ret = myStackCreate();
//	myStackPush(ret, 1);
//	myStackPop(ret);
//	myStackEmpty(ret);
//	return 0;
//}
//
//
////栈实现队列
//typedef struct Stack
//{
//	int *val;
//	int top;
//	int capacity;
//}Stack;
//
////栈初始化
//void StackInit(Stack* phead)
//{
//	assert(phead);
//	phead->capacity = 0;
//	phead->top = -1;
//	phead->val = NULL;
//}
////扩容
//void StackAddCapacity(Stack* phead)
//{
//	int newcapacity = phead->capacity == 0 ? 4 : phead->capacity * 2;
//	phead->capacity = newcapacity;
//	int* tmp = realloc(phead->val, sizeof(int)*newcapacity);
//	if (tmp == NULL)
//	{
//		perror("realloc");
//		exit(-1);
//	}
//	phead->val = tmp;
//}
////出栈
//void StackPop(Stack* phead)
//{
//	assert(phead);
//	assert(phead->top > -1);
//	phead->top--;
//}
////入栈
//void StackPush(Stack* phead, int x)
//{
//	assert(phead);
//	if (phead->top + 1 == phead->capacity)
//	{
//		StackAddCapacity(phead);
//	}
//	phead->val[phead->top + 1] = x;
//	phead->top++;
//}
////销毁
//void StackDestroy(Stack* phead)
//{
//	free(phead->val);
//	phead->val = NULL;
//	phead->top = -1;
//	phead->capacity = 0;
//}
////获取栈中有效元素个数
//int StackSize(Stack* phead)
//{
//	assert(phead);
//	return phead->top + 1;
//}
////检测栈是否为空,空为1，非空为0
//int StackEmpty(Stack* phead)
//{
//	assert(phead);
//
//	if (phead->top == -1)
//		return 1;
//	else
//		return 0;
//}
////获取栈顶元素
//int StackTop(Stack* phead)
//{
//	assert(phead);
//	assert(phead->top > -1);
//	return phead->val[phead->top];
//}
//
//
///////////
//typedef struct {
//	Stack ru;
//	Stack chu;
//} MyQueue;
//
//
//MyQueue* myQueueCreate() {
//	MyQueue* st = (MyQueue*)malloc(sizeof(MyQueue));
//	StackInit(&st->ru);
//	StackInit(&st->chu);
//	return st;
//}
//
//void myQueuePush(MyQueue* obj, int x) {
//	StackPush(&obj->ru, x);
//}
//
//int myQueuePop(MyQueue* obj) {
//	int ret;
//	if (StackEmpty(&obj->chu))
//	{
//		while (!StackEmpty(&obj->ru))
//		{
//			ret = StackTop(&obj->ru);
//			StackPush(&obj->chu, ret);
//			StackPop(&obj->ru);
//		}
//	}
//	ret = StackTop(&obj->chu);
//	StackPop(&obj->chu);
//	return ret;
//}
//
//int myQueuePeek(MyQueue* obj) {
//	int ret;
//	if (StackEmpty(&obj->chu))
//	{
//		while (!StackEmpty(&obj->ru))
//		{
//			ret = StackTop(&obj->ru);
//			StackPush(&obj->chu, ret);
//			StackPop(&obj->ru);
//		}
//	}
//	ret = StackTop(&obj->chu);
//	return ret;
//}
//
//bool myQueueEmpty(MyQueue* obj) {
//	return StackEmpty(&obj->ru) && StackEmpty(&obj->chu);
//}
//
//void myQueueFree(MyQueue* obj) {
//	StackDestroy(&obj->ru);
//	StackDestroy(&obj->chu);
//	free(obj);
//}


////循环队列
//typedef struct {
//	int* arr;
//	//用两个下标
//	int front;
//	int back;
//	int sz;//存放我们开辟循环队列的大小
//} MyCircularQueue;
//MyCircularQueue* myCircularQueueCreate(int k) {
//	MyCircularQueue* ret = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
//	ret->arr = (int*)malloc((k + 1)*sizeof(int));
//	ret->front = ret->back = 0;
//	ret->sz = k + 1;
//	return ret;
//}
//bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
//	//如果满了，则返回false，不再添加数据
//	if ((obj->back + 1) % obj->sz == obj->front)
//		return false;
//	//如果back移到了最后一个位置，存完数据就把back置零
//	if (obj->back == obj->sz - 1)
//	{
//		obj->arr[obj->back] = value;
//		obj->back = 0;
//	}
//	else
//	{
//		obj->arr[obj->back] = value;
//		obj->back++;
//	}
//	return true;
//}
//bool myCircularQueueDeQueue(MyCircularQueue* obj) {
//	//循环队列为空
//	if (obj->front == obj->back)
//		return false;
//	//删除到了最后一个位置
//	if (obj->front == obj->sz - 1)
//	{
//		obj->front = 0;
//	}
//	else
//	{
//		obj->front++;
//	}
//	return true;
//}
//int myCircularQueueRear(MyCircularQueue* obj) {
//	if (obj->front == obj->back)
//	{
//		return -1;
//	}
//	if (obj->back == 0)
//		return obj->arr[obj->sz - 1];
//	else
//		return obj->arr[obj->back - 1];
//
//}
//int myCircularQueueFront(MyCircularQueue* obj) {
//	if (obj->front == obj->back)
//	{
//		return -1;
//	}
//	return obj->arr[obj->front];
//}
//bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
//	if (obj->front == obj->back)
//		return true;
//	return false;
//}
//bool myCircularQueueIsFull(MyCircularQueue* obj) {
//	if ((obj->back + 1) % obj->sz == obj->front)
//		return true;
//	return false;
//}
//void myCircularQueueFree(MyCircularQueue* obj) {
//	free(obj->arr);
//	obj->arr = NULL;
//	free(obj);
//	obj = NULL;
//}
//int main()
//{
//	MyCircularQueue* obj = myCircularQueueCreate(3);
//	int a = myCircularQueueEnQueue(obj, 1);
//	a = myCircularQueueEnQueue(obj, 2);
//	a = myCircularQueueEnQueue(obj, 3);
//	a = myCircularQueueEnQueue(obj, 4);
//
//	int c=myCircularQueueRear(obj);
//	return 0;
//}


////求二叉树最大深度
//int calculateDepth(struct TreeNode* root) {
//	//空树返回0
//	if (root == NULL)
//		return 0;
//	//不是空树，记录左右两边子树的深度
//	int left = calculateDepth(root->left);
//	int right = calculateDepth(root->right);
//	//返回深度更大的+1，1是本身
//	return left>right ? left + 1 : right + 1;
//}
//
//
////判断两棵树是否相同
//bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
//	//如果两个节点都为空，则返回true
//	if (p == NULL&&q == NULL)
//		return true;
//	//通过上面代码，就说明至少两个没有全为空
//	//一个节点为空，一个不为空，则说不一样，直接返回false
//	if (p == NULL || q == NULL)
//		return false;
//	//两颗树的样子一样，值不同也要返回false
//	if (p->val != q->val)
//		return false;
//	//如果一切正常，就往下找左子树和右子树，若全部正常，就只会接收到两个空树而返回的true
//	return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
//}
//
//
////单值二叉树
//bool isUnivalTree(struct TreeNode* root) {
//	//空树返回true
//	if (root == NULL)
//		return true;
//	//判断左值是否和根相等
//	if (root&&root->left && (root->val != root->left->val))
//		return false;
//	//判断右值是否和跟相等
//	if (root&&root->right && (root->val != root->right->val))
//		return false;
//	//如果都相等则继续往下递归
//	return isUnivalTree(root->left) && isUnivalTree(root->right);
//}
//
//
////翻转二叉树（错误）
//int BinaryTreeSize(struct TreeNode* root)
//{
//	if (root == NULL)
//		return 0;
//	return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
//}
//struct TreeNode* DuiCheng(struct TreeNode* root, struct TreeNode* newroot)
//{
//	if (root == NULL)
//	{
//
//		newroot = NULL;
//		return newroot;
//	}
//	newroot->left = DuiCheng(root->right, newroot->left);
//	newroot->right = DuiCheng(root->left, newroot->right);
//	newroot->val = root->val;
//	return newroot;
//}
//struct TreeNode* Copy(struct TreeNode* root, struct TreeNode* newroot)
//{
//	if (root == NULL)
//	{
//		newroot = NULL;
//		return newroot;
//	}
//	newroot = root;
//	newroot->left = Copy(root->left, newroot->left);
//	newroot->right = Copy(root->right, newroot->right);
//	return newroot;
//}
//struct TreeNode* mirrorTree(struct TreeNode* root){
//	int size = BinaryTreeSize(root);
//	struct TreeNode* newroot = (struct TreeNode*)malloc(sizeof(struct TreeNode)*size);
//	newroot = root;
//	Copy(root, newroot);//先把箭头（链接）搞新树
//	DuiCheng(root, newroot);
//	return newroot;
//}
//
////144.翻转二叉树（正确写法）
//struct TreeNode* mirrorTree(struct TreeNode* root){
//	if (root == NULL)
//	{
//		return NULL;
//	}
//	//走一步创建一个节点
//	struct TreeNode* newnode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
//	newnode->val = root->val;
//	newnode->left = mirrorTree(root->right);
//	newnode->right = mirrorTree(root->left);
//	return newnode;
//}
//
////572. 另一棵树的子树
////判断两棵树是否相同
//bool isSame(struct TreeNode* root, struct TreeNode* subRoot)
//{
//	if (root == NULL&&subRoot == NULL)
//		return true;
//	if (root == NULL || subRoot == NULL)
//		return false;
//	if (root->val != subRoot->val)
//	{
//		return false;
//	}
//	return isSame(root->left, subRoot->left) && isSame(root->right, subRoot->right);
//}
//bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
//	//如果刚进函数或者root遍历到了NULL就返回false
//	if (root == NULL || subRoot == NULL)
//		return false;
//	//如果节点值相等了，进入判断后续是否完全相等
//	if (root->val == subRoot->val)
//	{
//		if (isSame(root, subRoot))
//			return true;
//	}
//	//只要有一个true最终都要是true，所以用||
//	return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
//}


//牛客二叉树遍历
//编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 
//例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。
//建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef char BTDataType;
typedef struct BinaryTreeNode {
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
} BTNode;
BTNode* per(char* arr, int* pi)
{
	if (arr[(*pi)] == '#')
	{
		(*pi)++;
		return NULL;
	}
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	root->_data = arr[(*pi)++];
	root->_left = per(arr, pi);
	root->_right = per(arr, pi);
	return root;
}
void mid(BTNode* root)
{
	if (root == NULL)
		return;
	mid(root->_left);
	printf("%c ", root->_data);
	mid(root->_right);
}
//int main() {
//	char arr[200];
//	scanf("%s", arr);
//	int i = 0;
//	BTNode* root = NULL;
//	root = per(arr, &i);
//	mid(root);
//	return 0;
//}
//
////7 - 6 输出二维数组每列最小数
//int main()
//{
//	int arr[10][10];
//	for (int i = 0; i<4; i++)
//	{
//		for (int j = 0; j<4; j++)
//		{
//			scanf("%d", &(arr[i][j]));
//		}
//	}
//	int min = 0;
//	for (int i = 0; i<4; i++)
//	{
//		min = arr[0][i];
//		for (int j = 0; j<4; j++)
//		{
//			if (min>arr[j][i])
//				min = arr[j][i];
//		}
//		printf("%d ", min);
//	}
//}
//

////二叉树的后序遍历
//int Sizetree(struct TreeNode* root)
//{
//	if (root == NULL)
//		return 0;
//	return Sizetree(root->left) + Sizetree(root->right) + 1;
//}
//void _postorderTraversal(struct TreeNode* root, int* arr, int* pi)
//{
//	if (root == NULL)
//		return;
//	_postorderTraversal(root->left, arr, pi);
//	_postorderTraversal(root->right, arr, pi);
//	arr[(*pi)++] = root->val;
//}
//int* postorderTraversal(struct TreeNode* root, int* returnSize) {
//	int size = Sizetree(root);
//	int* arr = (int*)malloc(sizeof(int)*size);
//	int i = 0;
//	_postorderTraversal(root, arr, &i);
//	*returnSize = size;
//	return arr;
//}
//
//
////二叉树的中序遍历
//int Sizetree(struct TreeNode* root)
//{
//	if (root == NULL)
//		return 0;
//	return Sizetree(root->left) + Sizetree(root->right) + 1;
//}
//void _inorderTraversal(struct TreeNode* root, int* arr, int* pi)
//{
//	if (root == NULL)
//		return;
//	_inorderTraversal(root->left, arr, pi);
//	arr[(*pi)++] = root->val;
//	_inorderTraversal(root->right, arr, pi);
//}
//int* inorderTraversal(struct TreeNode* root, int* returnSize) {
//	int sz = Sizetree(root);
//	int* arr = (int*)malloc(sizeof(int)*sz);
//	*returnSize = sz;
//	int i = 0;
//	_inorderTraversal(root, arr, &i);
//	return arr;
//}
//
//
////对称二叉树
//bool Issame(struct TreeNode* root1, struct TreeNode* root2)
//{
//	if (root1 == NULL&&root2 == NULL)
//	{
//		return true;
//	}
//	if (root1 == NULL || root2 == NULL)
//	{
//		return false;
//	}
//	if (root1->val != root2->val)
//		return false;
//	return Issame(root1->left, root2->right) && Issame(root1->right, root2->left);
//
//}
//bool isSymmetric(struct TreeNode* root) {
//	return Issame(root->left, root->right);
//}
//
//
////110. 平衡二叉树
////给定一个二叉树，判断它是否是高度平衡的二叉树。
////本题中，一棵高度平衡二叉树定义为：
////一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1
////算层数
//int leveSize(struct TreeNode* root1)
//{
//	if (root1 == NULL)
//		return 0;
//	int leftnum = leveSize(root1->left);
//	int rightnum = leveSize(root1->right);
//	return leftnum>rightnum ? leftnum + 1 : rightnum + 1;
//}
////递归判断每个节点
//bool _isBalanced(struct TreeNode* root)
//{
//	if (root == NULL)
//		return true;
//	int leftnum = leveSize(root->left);
//	int rightnum = leveSize(root->right);
//	if (leftnum>rightnum)
//	{
//		//不符合才返回false，如果符合则继续判断，不返回true
//		if (leftnum - rightnum>1)
//			return false;
//	}
//	if (rightnum - leftnum>1)
//		return false;
//	return _isBalanced(root->left) && _isBalanced(root->right);
//}
//bool isBalanced(struct TreeNode* root) {
//	return _isBalanced(root);
//}
//
//
//
//
////1171. 从链表中删去总和值为零的连续节点
//
////头插
//struct ListNode* headInsert(struct ListNode** head, int new_val)
//{
//	struct ListNode* Node = (struct ListNode*)malloc(sizeof(struct ListNode));
//	if (Node == NULL)
//		exit(-1);
//	Node->val = new_val;
//	Node->next = *head;
//	*head = Node;
//	return *head;
//}
////头删
//struct ListNode* Delete_(struct ListNode* prev, struct ListNode delete)
//
//	//删除节点(要传删除节点的前一个节点)
//struct ListNode* Delete_next(struct ListNode* prev, struct ListNode delete)
//{
//	prev->next = delete->next;
//	free(delete);
//	delete = NULL;
//}
//
//int IsSame(struct ListNode* head)
//{
//	struct ListNode* prev = head
//	struct ListNode* Now = prev->next;
//	struct ListNode* Next = now->next;
//	while (Now != NULL)
//	{
//		int i = Now->val;
//		int j = Next->val;
//		if (i == j)
//		{
//			Delete_next(i);
//		}
//	}
//}
//
//struct ListNode* removeZeroSumSublists(struct ListNode* head) {
//	//重复除去数字
//	while (IsSame(head))
//	{
//	}
//	return head;
//}
//
//
//
//
//
////LCP 44. 开幕式焰火
////「力扣挑战赛」开幕式开始了，空中绽放了一颗二叉树形的巨型焰火。 给定一棵二叉树 root 代表焰火，节点值表示巨型焰火这一位置的颜色种类。请帮小扣计算巨型焰火有多少种不同的颜色。
//typedef struct stack
//{
//	int*arr;
//	int sz;
//}stack;
//int Ishave(int val, stack*a)
//{
//	for (int i = 0; i<a->sz; i++)
//	{
//		if (val == a->arr[i])
//			return 0;
//	}
//	return 1;
//}
//void push(int val, stack*a)
//{
//	a->arr[a->sz] = val;
//	a->sz++;
//}
//void _numColor(struct TreeNode* root, stack* a)
//{
//	if (root == NULL)
//		return;
//	if (Ishave(root->val, a))
//	{
//		push(root->val, a);
//	}
//	_numColor(root->left, a);
//	_numColor(root->right, a);
//}
//
//int numColor(struct TreeNode* root){
//	stack a;
//	a.arr = malloc(sizeof(int) * 1005); a.sz = 0;
//	_numColor(root, &a);
//	return a.sz;
//}
//
//
////6 - 1 查找星期
//int getindex(char *s)
//{
//	if (strcmp(s, "Monday") == 0)
//		return 1;
//	else if (strcmp(s, "Wednesday") == 0)
//		return 3;
//	else if (strcmp(s, "Friday") == 0)
//		return 5;
//	else if (strcmp(s, "Sunday") == 0)
//	{
//		return 0;
//	}
//	else if (strcmp(s, "Saturday") == 0)
//	{
//		return 6;
//	}
//	else if (strcmp(s, "Thursday") == 0)
//	{
//		return 4;
//	}
//	else if (strcmp(s, "Tuesday") == 0)
//	{
//		return 2;
//	}
//	else
//		return -1;
//}
//
//
////7 - 2 考试座位号
////每个 PAT 考生在参加考试时都会被分配两个座位号，一个是试机座位，一个是考试座位。
////正常情况下，考生在入场时先得到试机座位号码，入座进入试机状态后，系统会显示该考生的考试座位号码，考试时考生需要换到考试座位就座。
////但有些考生迟到了，试机已经结束，他们只能拿着领到的试机座位号码求助于你，从后台查出他们的考试座位号码。
//struct text
//{
//	char xue[20];
//	int shi;
//	int kao;
//};
//int main()
//{
//	int n;
//	scanf("%d", &n);
//	struct text arr[n];
//	for (int i = 0; i<n; i++)
//	{
//		scanf("%s", arr[i].xue);
//		scanf("%d", &arr[i].shi);
//		scanf("%d\n", &arr[i].kao);
//	}
//	int m;
//	scanf("%d", &m);
//	int chi[m];
//	for (int i = 0; i<m; i++)
//	{
//		scanf("%d", &chi[i]);
//	}
//	for (int i = 0; i<m; i++)
//	{
//		for (int j = 0; j<n; j++)
//		{
//			if (arr[j].shi == chi[i])
//			{
//				printf("%s %d\n", arr[j].xue, arr[j].kao);
//				break;
//			}
//		}
//	}
//	return 0;
//}
//
//
//
////7 - 3 时间换算
////本题要求编写程序，以hh : mm : ss的格式输出某给定时间再过n秒后的时间值（超过23 : 59 : 59就从0点开始计时）。
//int main()
//{
//	int shi, fen, miao;
//	int add;
//	scanf("%d:%d:%d\n%d", &shi, &fen, &miao, &add);
//	//printf("%d %d %d %d",shi,fen,miao,add);
//	miao += add;
//	while (miao >= 60)
//	{
//		miao -= 60;
//		fen++;
//		if (fen >= 60)
//		{
//			shi++;
//			if (shi>23)
//			{
//				shi = 0;
//			}
//			fen = 0;
//		}
//	}
//	printf("%02d:%02d:%02d", shi, fen, miao);
//	return 0;
//}
//
//
//
////7 - 4 通讯录排序
////输入n个朋友的信息，包括姓名、生日、电话号码，本题要求编写程序，按照年龄从大到小的顺序依次输出通讯录。题目保证所有人的生日均不相同。
//struct friend
//{
//	char xing[10];
//	int chusheng;
//	char dian[20];
//};
//int main()
//{
//	int n;
//	scanf("%d", &n);
//	struct friend arr[n];
//	for (int i = 0; i<n; i++)
//	{
//		scanf("%s %d %s\n", arr[i].xing, &arr[i].chusheng, arr[i].dian);
//		//printf("%s %d %s\n",arr[i].xing,arr[i].chusheng,arr[i].dian);
//	}
//	for (int i = 0; i<n; i++)
//	{
//		for (int j = i + 1; j<n; j++)
//		{
//			if (arr[j].chusheng<arr[i].chusheng)
//			{
//				struct friend tmp = arr[i];
//				arr[i] = arr[j];
//				arr[j] = tmp;
//			}
//		}
//	}
//	for (int i = 0; i<n; i++)
//	{
//		printf("%s %d %s\n", arr[i].xing, arr[i].chusheng, arr[i].dian);
//	}
//	return 0;
//}



//使用结构体实现
//编写程序，实现如下功能：
//
//（1）在main()函数中，通过键盘，按学号顺序，依次输入每个同学名字（自定）、3门课成绩（可以在word文档上准备好相关信息，复制 - 粘贴的方式使用）；
//
//（2）编写一个函数，统计A课、B课、C课各门课程的最高分、最低分、平均分、及格率（百分数表示），在main()函数中打印输出结果；
//
//（3）编写一个函数，计算每个同学期末考试总分，并按总分降序排序。在main()中按格式“学号 姓名 A课成绩 B课成绩 C课成绩 总分”输出排序后的信息；
//
//（4）如果至少有两门课成绩<60分，输出这样同学的学号及姓名；如果没有这样的情况，则输出“没有至少两门课成绩<60分同学的记录”；
//
//（5）提示：“请输入您要查找的同学的学号（输入0查询结束）”，当输入学号后，调用函数，实现查询，在main()中输出查询结果“学号 姓名 总成绩排名”或者“查无此人”。直到输入“0”结束查询
//#include<stdio.h>
//#include<string.h>
//struct student
//{
//	char name[20];
//	char xue[20];
//	int cj[3];//0a  1b  2c
//	int zong;
//};
//struct score
//{
//	int max;
//	int min;
//	double ping;
//	double jige;
//};
////j=要找的科目下标 
//void Tongji(struct score* s, struct student* stu, int j)
//{
//	(*s).max = stu[0].cj[j];
//	s->min = stu[0].cj[j];
//	int sum = 0;
//	int j_num = 0;
//	//遍历所有人 
//	for (int i = 0; i<15; i++)
//	{
//		if (s->max<stu[i].cj[j])
//		{
//			s->max = stu[i].cj[j];
//		}
//		if (s->min>stu[i].cj[j])
//		{
//			s->min = stu[i].cj[j];
//		}
//		if (stu[i].cj[j]>60)
//		{
//			j_num++;
//		}
//		sum += stu[i].cj[j];
//	}
//	s->ping = 1.0*sum / 15;
//	s->jige = 1.0*j_num / 15;
//
//}
//void paixu(struct student * stu)
//{
//	for (int i = 0; i<15; i++)
//	{
//		for (int j = 0; j<15 - 1 - i; j++)
//		{
//			if (stu[j].zong<stu[j + 1].zong)
//			{
//				struct student tmp = stu[j + 1];
//				stu[j + 1] = stu[j];
//				stu[j] = tmp;
//			}
//		}
//	}
//}
//int cha(struct student* stu, char arr[])
//{
//	for (int i = 0; i<15; i++)
//	{
//		if (strcmp(stu[i].xue, arr) == 0)
//			return i;
//	}
//	return 0;
//}
////学号3210001~3210015
//int main()
//{
//	struct student stu[15];
//	for (int i = 0; i<15; i++)
//	{
//		scanf("%s %s\n", stu[i].name, stu[i].xue);
//		scanf("%d", &stu[i].cj[0]);
//		scanf("%d", &stu[i].cj[1]);
//		scanf("%d", &stu[i].cj[2]);
//		//getchar();
//		stu[i].zong = stu[i].cj[0] + stu[i].cj[1] + stu[i].cj[2];
//	}
//
//	 struct score s1;
//	 Tongji(&s1,stu,0);//a
//	 printf("a  最高分：%d 最低分：%d 平均分：%.1lf 及格率：%.1lf%%\n",s1.max,s1.min,s1.ping,s1.jige*100);
//	 Tongji(&s1,stu,1);//b
//	 printf("b  最高分：%d 最低分：%d 平均分：%.1lf 及格率：%.1lf%%\n",s1.max,s1.min,s1.ping,s1.jige*100);
//	 Tongji(&s1,stu,2);//c
//	 printf("c  最高分：%d 最低分：%d 平均分：%.1lf 及格率：%.1lf%%\n",s1.max,s1.min,s1.ping,s1.jige*100);
//	 paixu(stu);
//	 for(int i=0;i<15;i++)
//	 {
//	 	printf("姓名：%s 学号：%s a：%d b：%d c：%d 总分：%d\n",stu[i].name,stu[i].xue,stu[i].cj[0],stu[i].cj[1],stu[i].cj[2],stu[i].zong);
//	 }
//
//	 int flag=0;
//	 for(int i=0;i<15;i++)
//	 {
//	 	int num=0;
//	 	for(int j=0;j<3;j++)
//	 	{
//	 		if(stu[i].cj[j]<60)
//	 		{
//	 			num++;
//	 		}
//	 	}
//	 	if(num>=2)
//	 	{
//	 		flag++;
//	 		printf("姓名：%s 学号：%s\n",stu[i].name,stu[i].xue);
//	 	}
//	 }
//	 if(flag==0)
//	 	printf("没有至少两门课成绩<60分同学的记录\n");
//
//	char arr[20];
//	while (1)
//	{
//		printf("请输入您要查找的同学的学号（输入0查询结束）\n");
//		scanf("%s", arr);
//		if (strcmp(arr, "0") == 0)
//			break;
//		int c = cha(stu, arr);
//		if (c)
//		{
//			printf("学号：%s 姓名：%s 成绩总排名：%d\n", stu[c].xue, stu[c].name, c + 1);
//		}
//		else{
//			printf("查无此人\n");
//		}
//	}
//	return 0;
//}
//
//

//
//#include<stdio.h>
//#include<string.h>
//struct stu
//{
//	char xh[20];
//	char name[20];
//	int cj[3];
//	int sum;
//}cc;
//struct score
//{
//	int max;
//	int min;
//	double avr;
//	double jg;
//}b[3];
//void paixu(struct stu *c){
//	int i, j;
//	for (i = 0; i<14; i++){
//		for (j = i; j<15; j++){
//			if (c[i].sum<c[j].sum){
//				cc = c[i];
//				c[i] = c[j];
//				c[j] = cc;
//			}
//		}
//	}
//}
//int cha(struct stu* c, char arr[])
//{
//	for (int i = 0; i<15; i++)
//	{
//		if (strcmp(c[i].xh, arr) == 0)
//			return i;
//	}
//	return 0;
//}
//void caculate(struct stu *c){
//	int i, j;
//	double sum = 0;
//	for (j = 0; j<3; j++){
//		int jgr = 0;
//		int max = -1, min = 101;
//		sum = 0;
//		for (i = 0; i<15; i++){
//			sum += c[i].cj[j];
//			if (c[i].cj[j]>max)
//				max = c[i].cj[j];
//			if (c[i].cj[j]<min)
//				min = c[i].cj[j];
//			if (c[i].cj[j]>=60)
//				jgr += 1;
//		}
//		b[j].max = max;
//		b[j].min = min;
//		b[j].avr = sum / 15;
//		b[j].jg = jgr * 100 / 15;
//	}
//}
//main(){
//	int i, j, flag = 0;
//	struct stu c[15];
//	for (i = 0; i<15; i++){
//		scanf("%s", c[i].xh);
//		scanf("%s", c[i].name);
//		scanf("%d", &c[i].cj[0]);
//		scanf("%d", &c[i].cj[1]);
//		scanf("%d", &c[i].cj[2]);
//		c[i].sum = c[i].cj[0] + c[i].cj[1] + c[i].cj[2];
//	}
//
//	caculate(c);
//	printf("A课最高分%d ", b[0].max);
//	printf("A课最低分%d ", b[0].min);
//	printf("A课平均分%.1lf ", b[0].avr);
//	printf("A课及格率%.1lf%%\n", b[0].jg);
//	printf("B课最高分%d ", b[1].max);
//	printf("B课最低分%d ", b[1].min);
//	printf("B课平均分%.1lf ", b[1].avr);
//	printf("B课及格率%.1lf%%\n", b[1].jg);
//	printf("C课最高分%d ", b[2].max);
//	printf("C课最低分%d ", b[2].min);
//	printf("C课平均分%.1lf ", b[2].avr);
//	printf("C课及格率%.1lf%%\n", b[2].jg);
//	paixu(c);
//	for (int i = 0; i<15; i++){
//		printf("%s ", c[i].xh);
//		printf("%s ", c[i].name);
//		printf("%d ", c[i].sum);
//	}
//	for (i = 0; i<15; i++){
//		int bjg = 0;
//		for (j = 0; j<3; j++){
//			if (c[i].cj[j]<60)
//				bjg++;
//		}
//		if (bjg >= 2){
//			printf("%s %s\n", c[i].xh, c[i].name);
//			flag = 1;
//		}
//	}
//	if (flag == 0) printf("没有至少两门课成绩<60分同学的记录\n");
//	char arr[20];
//	while (1){
//		printf("请输入要查询的学号\n");
//		scanf("%s", arr);
//		if (strcmp(arr, "0") == 0) break;
//		int aaa = cha(c, arr);
//		if (aaa)
//		{
//			printf("%s %s 排名为%d\n", c[aaa].xh, c[aaa].name, aaa + 1);
//		}
//		else
//			printf("查无此人\n");
//	}
//}




#include<stdio.h>
#include<string.h>
#include<math.h>
struct stu
{
	char xh[20];
	char name[20];
	int cj[3];
	int sum;
}cc;
void shanchu(struct stu *c, int n){
	int i;
	for (i = n; i<10; i++){
		c[i] = c[i + 1];
	}
}
main(){
	int i, j;
	int max = 0;
	int index = 0;
	struct stu c[15];
	for (i = 0; i<10; i++){
		scanf("%s ", c[i].xh);
		scanf("%s ", c[i].name);
		scanf("%d", &c[i].cj[0]);
		scanf("%d", &c[i].cj[1]);
		scanf("%d", &c[i].cj[2]);
		c[i].sum = c[i].cj[0] + c[i].cj[1] + c[i].cj[2];
	}
	for (int i = 0; i<10; i++){
		printf("%s ", c[i].xh);
		printf("%s ", c[i].name);
		printf("%d ", c[i].cj[0]);
		printf("%d ", c[i].cj[1]);
		printf("%d\n", c[i].cj[2]);
	}
	for (i = 0; i<10; i++){
		if (c[i].sum >= max) {
			max = c[i].sum;
			index = i;
		}
	}
	printf("转入浙江大学的同学是 %s %s\n", c[index].xh, c[index].name);
	shanchu(c, index);
	for (i = 0; i<9; i++){
		printf("%s ", c[i].xh);
		printf("%s ", c[i].name);
		printf("%d ", c[i].cj[0]);
		printf("%d ", c[i].cj[1]);
		printf("%d\n", c[i].cj[2]);

	}
}

 //3210001 张一 95 86 71 
 //3210002 张二 87 100 69 
 //3210003 张三 99 54 62 
 //3210004 张四 57 84 62
 //3210005 张五 87 58 95
 //3210006 张六 87 59 67 
 //3210007 张七 87 68 58 
 //3210008 张八 57 59 64 
 //3210009 张九 54 68 69 
 //3210010 张十 87 98 57



//PTA

//6 - 1 学生成绩比高低
int compareScore(const struct Student *s1, const struct Student *s2)
{
	int sum1 = s1->C + s1->English;
	int sum2 = s2->C + s2->English;
	if (sum1>sum2)
		return 1;
	else if (sum1<sum2)
		return -1;
	else
	{
		if (s1->C>s2->C)
			return 1;
		else if (s1->C<s2->C)
			return -1;
		else
		{
			if (s1->English>s2->English)
				return 1;
			else if (s1->English<s2->English)
				return -1;
			else
			{
				return 0;
			}
		}
	}
}


//6 - 2 军事体能成绩统计（成绩复核）
int input_data(struct stu s[])
{
	int n;
	scanf("%d", &n);
	for (int i = 0; i<n; i++)
	{
		scanf("%s%d%d%d%d%d\n", s[i].name, &s[i].no, &s[i].lift, &s[i].s_run, &s[i].km_3, &s[i].updn);
	}
	return n;
}
void process(struct stu s[], int n, struct stu s1)
{
	int flag = 0;
	for (int i = 0; i<n; i++)
	{
		if (s[i].no == s1.no)
		{
			if (s[i].lift == s1.lift&&
				s[i].s_run == s1.s_run&&
				s[i].km_3 == s1.km_3&&
				s[i].updn == s1.updn)
			{
				printf("%s,%d,复核成功,成绩不变\n", s1.name, s1.no);
				flag = 1;
				break;
			}
			else
			{
				s[i] = s1;
				printf("%s,%d,复核成功,成绩修改\n", s1.name, s1.no);
				flag = 1;
				break;
			}
		}
	}
	if (flag == 0)
		printf("%s,%d,复核失败,无此人\n", s1.name, s1.no);
}